← 返回题目列表

AtCoder · kupc2020_f

F. 网格

中文机器翻译题面 查看原题

配点 : 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