Rain#4307
Batumi's weather can be unpredictable: sometimes a sudden storm hits the city. Rezo, one of the organizers of the Vekua Cup, was waiting at the bus station for guests arriving on an intercity bus when a heavy rain began. As the bus station was under renovation, it was impossible to stay inside, and staying outside in the rain was also not an option. Rezo noticed the complete schedule of the city bus for all stops displayed on the wall. He planned to board the bus at the station, travel a few stops, then catch a return bus on the same route to get back to the station before the guests arrived. Rezo wants to minimize the amount of time he spends in the rain.
Your task is to calculate this minimum time.
The first line of input contains integers: t_1, t_2, , n_1, n_2 (0 \leq t_1 \leq t_2 \leq 10^9, 2 \leq m \leq 1000, n_1 \geq 1, n_2 \geq 1, m \cdot (n_1 + n_2) \leq 10^6).
Here, t_1 is the time the rain starts, t_2 is the time the guests arrive at the bus station, is the number of stops on the city bus route (including the bus station), and n_1 and n_2 are the number of city bus trips departing from and arriving at the bus station, respectively. The route's terminals are the bus station (stop ) and stop number , and staying on the bus at the end terminal is not allowed.
Next, lines follow, each containing n_1+n_2 non-negative integers (not exceeding 10^9), representing the schedule for each stop in order from the bus station to the terminal stop. For each stop, the first n_1 numbers are the departure times of buses leaving the bus station: the -th number represents the arrival and departure time of the -th "forward" trip at that stop. The next n_2 numbers are the times for buses returning to the bus station: the (n_1+i)-th number represents the departure time of the -th "return trip" from that stop.
It is assumed that a bus both arrives at and leaves a stop at the same time instant. Rezo can transfer from one bus to another only if the arrival time of the first bus at the stop is not later than the arrival time of the second bus.
Output a single integer: the minimum time Rezo will have to spend in the rain before the guests arrive.
Example 1