34222번 - 길 걷기

문제

준혁이는 한양대의 지도를 $N$행 $M$열을 가지는 배열로 나타냈다. 배열의 각 칸에는 건물이 있다.

각 건물 1ドル \le i \le N; 1 \le j \le M-1$을 만족하는 모든 건물은 2ドル$개의 건물로 이동하는 길이 있다.

• 건물 $(i,j)$에서 $(A_{i,j},j+1)$로 이동한다. 이 길의 길이는 $a_{i,j}$이다.
• 건물 $(i,j)$에서 $(B_{i,j},j+1)$로 이동한다. 이 길의 길이는 $b_{i,j}$이다.

1ドル$번 열의 모든 건물에는 학생이 위치해 있다. $i$번째 학생은 $(i,1)$에 위치해 있으며 총 $N$명의 학생이 있다. $i$번째 학생은 건물과 연결되어 있는 길을 지나 최종적으로 $M$번째 열로 이동한다. 1ドル$번째 학생이 먼저 출발하며 1ドル$번째 학생이 $M$번째 열의 어떤 건물로 도착했다면 2ドル$번째 학생이 출발하고, $\ldots,ドル $N$번째 학생까지 순서대로 $i$번째 학생은 $i-1$번째 학생이 $M$번째 열에 도착한 이후 출발한다. 학생들은 새로운 건물을 가는 것을 좋아하기 때문에, 어떤 학생이 이미 방문한 건물로는 이동하지 않는다.

$N$번째 학생까지 모두 도착한 이후 $i$번째 학생이 이동한 길의 길이의 합을 $f(i)$라고 하자. 모든 학생들이 이미 방문한 건물을 방문하지 않고 모두 $M$번째 열에 도착할 수 있는지 구해보고 가능하다면 학생들의 이동 경로를 최적으로 설정하였을 때 $f(1) + f(2) + \ldots + f(N)$의 최솟값을 구해보자.

입력

첫째 줄에 $N$과 $M$이 공백으로 구분되어 주어진다. $(2 \leq N, M \leq 500,000円; N \times M \le 1,000円,000円)$

이후 $N$개의 줄에 걸쳐 $i+1$번째 줄에 $A_{i,1}, A_{i,2}, \ldots, A_{i,M-1}$이 공백으로 구분되어 주어진다. $(1 \leq A_{i,j} \leq N)$

이후 $N$개의 줄에 걸쳐 $i+N+1$번째 줄에 $B_{i,1}, B_{i,2}, \ldots, B_{i,M-1}$이 공백으로 구분되어 주어진다. $(1 \leq B_{i,j} \leq N)$

이후 $N$개의 줄에 걸쳐 $i+2N+1$번째 줄에 $a_{i,1}, a_{i,2}, \ldots, a_{i,M-1}$이 공백으로 구분되어 주어진다. $(0 \leq a_{i,j} \leq 10^9)$

이후 $N$개의 줄에 걸쳐 $i+3N+1$번째 줄에 $b_{i,1}, b_{i,2}, \ldots, b_{i,M-1}$이 공백으로 구분되어 주어진다. $(0 \leq b_{i,j} \leq 10^9)$

출력

첫째 줄에 $f(1) + f(2) + \ldots + f(N)$의 최솟값을 출력한다. 만약 모든 학생들이 조건을 만족하며 $M$열에 도달할 수 없다면 -1을 대신 출력한다.

제한

힌트