버스

존은 친구를 만나려고 버스 차고지(종점)에 일찍 도착했다. 친구는 나중에 오고 밖은 춥기 때문에, 존은 그냥 기다리는 대신 버스를 타고 노선을 따라 몇 정거장 갔다가 다른 버스로 갈아타고 친구가 오기 전에 차고지로 돌아오려고 한다.

존은 기다리는 총 시간을 최소로 하고 싶다. 이 시간은 다음 세 가지의 합이다.

• 나가는 버스를 타기 전 차고지에서 기다린 시간,
• 돌아오는 지점에서 버스를 갈아타려고 기다린 시간,
• 차고지로 돌아온 뒤 친구를 기다린 시간.

존은 시간을 잘 지키므로 늦으면 안 된다. 즉 친구가 도착하는 시각보다 늦지 않게 차고지로 돌아와야 한다. 도착 시각들과 버스 시간표를 읽어 존이 기다리는 최소 총 시간을 출력하는 프로그램을 작성하시오.

첫째 줄에 다섯 정수 $t_1$, $t_2$, $m$, $n_1$, $n_2$가 공백 하나로 구분되어 주어진다. 이때 $0 \le t_1 \le t_2 \le 10^9$, $2 \le m \le 1000$, $n_1, n_2 \ge 1$, $m \times (n_1 + n_2) \le 10^6$이다.

• $t_1$: 존이 차고지에 도착하는 시각,
• $t_2$: 친구가 차고지에 도착하는 시각,
• $m$: 차고지를 포함한 노선의 정거장 수,
• $n_1$: 차고지에서 출발하는 버스의 수,
• $n_2$: 차고지로 들어오는 버스의 수.

다음 $m$개의 줄에는 정거장별 시간표가 정거장 순서대로 주어진다. 정거장 $1$이 차고지이고, 그다음이 정거장 $2, \dots, m$이다. 나가는 버스는 $1 \to 2 \to \dots \to m$ 순서로, 들어오는 버스는 $m \to \dots \to 2 \to 1$ 순서로 운행한다. 각 정거장의 줄에는 $n_1 + n_2$개의 정수 $x_{ij}$ ($0 \le x_{ij} \le 10^9$)가 있다. 앞의 $n_1$개는 그 정거장에서 나가는 버스 $n_1$대의 시각이고, 나머지 $n_2$개는 그 정거장에서 들어오는 버스 $n_2$대의 시각이다.

모든 버스는 이웃한 두 정거장 사이를 이동하는 데 최소 $1$의 시간이 걸린다. 존은 어떤 버스가 그 정거장을 지나는 시각에 그곳에 있어야만 그 정거장에서 그 버스를 탈 수 있다. 한 정거장에서 두 버스가 각각 시각 $t_a$, $t_b$에 있을 때, 그 정거장에서 앞 버스에서 뒤 버스로 갈아타는 것은 $t_a \le t_b$일 때에만 가능하다.

존이 기다려야 하는 최소 총 시간을 정수 하나로 출력한다. 왕복이 가능하고 친구가 도착하기 전에 돌아올 수 있게 하는 버스 조합이 없으면, 존은 차고지에서 내내 기다리므로 답은 $t_2 - t_1$이다.

예시에서 최적의 계획은 다음과 같다. 시각 $0$에 차고지에서 나가는 버스를 타고, 정거장 $2$에서 내린 뒤, 시각 $4$에 들어오는 버스로 갈아타서, 시각 $9$에 차고지로 돌아온다. 기다린 시간은 차고지에서 $0$, 갈아탈 때 $1$, 친구를 기다리며 $1$로 모두 합쳐 $2$이다.