격자 그래프를 고려해 봅시다. 정점들은 $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$인 양방향 간선이 존재합니다.
• 그래프에는 다른 간선이 존재하지 않습니다.

이 그래프의 최소 신장 트리(MST)에 포함된 간선들의 총 가중치를 구하십시오.

입력

첫 번째 줄에는 두 양의 정수 $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$에 대하여 $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비트 정수형에 담기지 않을 수 있음에 유의하십시오.

예제

입력 1

2 3
1
1 3 6
1 4
1 2

출력 1

17

입력 2

4 3
1 13 15
3 6 11
3 6 6 11
9 17

출력 2

173