配点 : 300 点
問題文
顶点是 我有一个带有 H 行 W 列的网格图。
从上面 i 第 j 番目 (1 \le i \le H, 1 \le j \le W) 的顶点 表示为 (i, j) 。
広義単調増加 正整数序列 A, B, C, D 每个长度是 H-1, W, H, W-1 。
頂点 (i, j) 和顶点 询问 (i+1, j) 的重量为 它们通过无向边 A_i + B_j 连接。(1 \le i \le H-1, 1 \le j \le W)
頂点 (i, j) 和顶点 询问 (i, j+1) 的重量为 它们通过无向边 C_i + D_j 连接。(1 \le i \le H, 1 \le j \le W-1)
不存在其他边。
求该图的最小生成树中包含的边的权重之和。
制約
- 2 \le H \le 10^5
- 2 \le W \le 10^5
- 1 \le A_i \le 10^6 (1 \le i \le H-1)
- 1 \le B_j \le 10^6 (1 \le j \le W)
- 1 \le C_i \le 10^6 (1 \le i \le H)
- 1 \le D_j \le 10^6 (1 \le j \le W-1)
- A_i \le A_{i+1} (1 \le i \le H-2)
- B_j \le B_{j+1} (1 \le j \le W-1)
- C_i \le C_{i+1} (1 \le i \le H-1)
- D_j \le D_{j+1} (1 \le j \le W-2)
入力
输入是按以下格式从标准输入给出的。
H W
A_1 A_2 \ldots A_{H-1}
B_1 B_2 \ldots B_{W-1} B_W
C_1 C_2 \ldots C_{H-1} C_H
D_1 D_2 \ldots D_{W-1}
出力
输出网格图的最小生成树中包含的边的权重之和。
请注意,答案可能不适合 32 位整数。
入力例 1
2 3 1 1 3 6 1 4 1 2
出力例 1
17

给定的图表将如上图所示。
该图的最小生成树中包含的边的权重之和为 17 。
入力例 2
4 3 1 13 15 3 6 11 3 6 6 11 9 17
出力例 2
173