그리드의 최소 신장 트리 구하기

시간 제한2초메모리 제한512 MB

요약

네 개의 비감소 수열로 간선 가중치가 정해지는 격자 그래프에서 최소 신장 트리의 총 가중치를 구한다.

난이도: 어려움10점 중 8점
유형: 최소 신장 트리, 그리디, 정렬, 구현
정답자: 아직 제출이 없습니다

문제

그리드 그래프를 생각하자. 정점은 $H$ 개의 행과 $W$ 개의 열로 이루어진 격자에 배치되어 있다. $i$ 번째 행, $j$ 번째 열에 있는 정점을 $(i, j)$ 로 표기한다.

그래프 간선의 가중치를 정의하기 위해, 각각 $H-1$ , $W$ , $H$ , $W-1$ 개의 양의 정수로 이루어진 네 개의 비감소 수열 $A$ , $B$ , $C$ , $D$ 를 생각하자.

$1 \le i \le H-1$ 과 $1 \le j \le W$ 를 만족하는 모든 $i$ 와 $j$ 에 대해, 정점 $(i, j)$ 와 $(i+1, j)$ 를 잇는 가중치 $A\_i + B\_j$ 의 양방향 간선이 있다.
$1 \le i \le H$ 와 $1 \le j \le W-1$ 을 만족하는 모든 $i$ 와 $j$ 에 대해, 정점 $(i, j)$ 와 $(i, j+1)$ 을 잇는 가중치 $C\_i + D\_j$ 의 양방향 간선이 있다.
그래프에는 다른 간선이 없다.

이 그래프의 최소 신장 트리에 포함된 간선들의 가중치 합을 구하라.

입력

입력의 첫째 줄에는 두 양의 정수 $H$ 와 $W$ 가 주어진다. ( $2 \le H, W \le 10^5$ )

둘째 줄에는 수열 $A$ 의 원소인 $H-1$ 개의 정수 $A\_i$ 가 주어진다.

셋째 줄에는 수열 $B$ 의 원소인 $W$ 개의 정수 $B\_i$ 가 주어진다.

넷째 줄에는 수열 $C$ 의 원소인 $H$ 개의 정수 $C\_i$ 가 주어진다.

다섯째 줄에는 수열 $D$ 의 원소인 $W-1$ 개의 정수 $D\_i$ 가 주어진다.

$i>1$ 인 모든 $i$ 에 대해 $A\_{i-1} \le A\_{i}$ , $B\_{i-1} \le B\_{i}$ , $C\_{i-1} \le C\_{i}$ , $D\_{i-1} \le D\_{i}$ 가 성립하며, 추가로 $1 \le A\_i, B\_i, C\_i, D\_i \le 10^6$ 임이 보장된다.

출력

주어진 그래프의 최소 신장 트리에 포함된 간선들의 가중치 합을 출력한다. 답이 32비트 정수의 범위를 넘을 수 있음에 유의하라.

예제2

예제 1
입력
```
2 3
1
1 3 6
1 4
1 2
```
예상 출력
```
17
```
예제 2
입력
```
4 3
1 13 15
3 6 11
3 6 6 11
9 17
```
예상 출력
```
173
```