F - GRIDMST Editorial /

Time Limit: 2 sec / Memory Limit: 1024 MB

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

出力

グリッドグラフの最小全域木に含まれる辺の重みの和を出力せよ。

答えは 32bit 整数に収まらない可能性があることに注意せよ。

入力例 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