8378번 - Buses 다국어

Little John is planning to make a trip with his friend to the museum. They arranged a meeting at the bus depot. John is a very punctual person, so he arrived at the bus depot too early. It is cold outside, so John decided to wait for his colleague in a bus. Unfortunately, all buses stop at the depot only for a while, so John decided to get on one of the buses, travel a couple of bus stops and then switch back to a bus going back to the depot. Because of bad weather, John would like to spend outside as little time as possible. In order to obtain this goal, he would like to minimize the total time he will wait for the bus at the depot, the time he will wait for his friend after getting back to the depot and the time he will spend waiting for the change of buses. As we already know, John is very punctual and so he would not like to be late for meeting his friend. John found a detailed timetable of all buses, which will let him plan the ride. He is not a great mathematical however, so he asked you to solve the problem for him.

Write a program which:

• reads from the standard input the moments of John's and his friend's arrivals and the bus timetable,
• calculates the shortest possible time, which John has to spend outside waiting for his friend,
• writes the result to the standard output.

In the first line of the standard input there are five integers: t₁, t₂, m, n₁, n₂ (0 ≤ t₁ ≤ t₂ ≤ 1 000 000 000, 2 ≤ m ≤ 1 000, n₁, n₂ ≥ 1, m × (n₁ + n₂) ≤ 1 000 000), separated by single spaces. These numbers represent adequately: the moment of John's arrival to the bus depot, the moment of John's friend's arrival to the bus depot, the number of bus stops on the route (including the bus depot), the number of buses departing from the bus depot and the number of buses arriving at the depot. The following m lines contain bus timetables for the consecutive bus stops. The first bus stop is the depot. Buses departing from the depot stop at the stops 1, 2, ..., m. Buses arriving at the depot stop at the stops m, ..., 2, 1. Each bus after arriving to the first or m-th stop finishes its course for the considered day. The timetable for the i-th bus stop consists of n₁ + n₂ integers 0 ≤ x_ij ≤ 1 000 000 000, where x_ij represents the time of arrival / departure of the j-th bus. These numbers are separated within each line by single spaces. For j ≤ n₁ the number is related to the bus departing from the bus depot, and for j > n₁ - the bus arriving at the depot. Arrival and departure of each bus at every stop take place in the same time unit. Each bus needs at least one time unit to travel between any two consecutive bus stops. John can get on a bus assuming that he is at the appropriate bus stop at the time of the bus's departure. In particular, switching from bus A to bus B, provided that the moments of their arrival at the bus stop are adequately t_a and t_b, is possible if t_a ≤ t_b.

The first and only line of the standard output should contain one integer - the minimal time that John has to spend outside waiting for his friend. If there are no busses allowing John to perform planned maneuver, you should assume that John will spend all the time waiting at the depot.

In the solution minimizing John's time of waiting outside, he is required to: get on the first bus at the depot in the zero time unit, get off at the second bus stop, get on the second bus in the fourth time unit and be back at the depot in the ninth time unit.