Buses

John arrives at a bus depot early to meet a friend. The friend will arrive later, and it is cold outside, so instead of waiting the whole time John wants to ride a bus a few stops down the route and take another bus back to the depot before his friend shows up.

He wants to minimize the total time he spends waiting, which is the sum of three parts:

• the time he waits at the depot before boarding the outbound bus,
• the time he waits to change buses at the stop where he turns around, and
• the time he waits for his friend after returning to the depot.

John is punctual and must not be late: he has to be back at the depot no later than his friend's arrival time. Write a program that reads the arrival times and the bus timetable and prints the shortest possible total waiting time.

The first line contains five integers $t_1$, $t_2$, $m$, $n_1$, $n_2$ separated by single spaces, where $0 \le t_1 \le t_2 \le 10^9$, $2 \le m \le 1000$, $n_1, n_2 \ge 1$, and $m \times (n_1 + n_2) \le 10^6$:

• $t_1$: the moment John arrives at the depot,
• $t_2$: the moment his friend arrives at the depot,
• $m$: the number of stops on the route, including the depot,
• $n_1$: the number of buses that depart from the depot,
• $n_2$: the number of buses that arrive at the depot.

The next $m$ lines give the timetable, one line per stop, in order: stop $1$ is the depot, then stops $2, \dots, m$. Outbound buses run $1 \to 2 \to \dots \to m$; inbound buses run $m \to \dots \to 2 \to 1$. Each stop's line has $n_1 + n_2$ integers $x_{ij}$ with $0 \le x_{ij} \le 10^9$: the first $n_1$ values are the times of the $n_1$ outbound buses at that stop, and the remaining $n_2$ values are the times of the $n_2$ inbound buses at that stop.

Every bus needs at least one time unit to travel between two consecutive stops. John boards a bus at a stop only if he is present at that bus's time for the stop. Changing from one bus to another at a stop, where the two buses are there at times $t_a$ and $t_b$, is possible only if $t_a \le t_b$.

Print a single integer: the minimum total time John has to spend waiting. If no pair of buses lets him make the round trip and return by his friend's arrival, he waits at the depot the whole time, so the answer is $t_2 - t_1$.

In the example, the optimal plan is: board the outbound bus at the depot at time $0$, get off at stop $2$, board the inbound bus at time $4$, and arrive back at the depot at time $9$. The waiting time is $0$ at the depot, $1$ to change buses, and $1$ for the friend, which is $2$ in total.