AT_kupc2020_f GRIDMST

[problemUrl]: https://atcoder.jp/contests/kupc2020/tasks/kupc2020_f 頂点が $ 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) $ これら以外の辺は存在しません。 このグラフの最小全域木に含まれる辺の重みの和を求めてください。

入力は以下の形式で標準入力から与えられる。 > $ 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 整数に収まらない可能性があることに注意せよ。

### 制約 - $ 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) $ ### Sample Explanation 1 !\[\](https://img.atcoder.jp/kupc2020/gridmst-sample.png) 与えられたグラフは上の図のようになります。 このグラフの最小全域木に含まれる辺の重みの和は $ 17 $ です。