頂点が $H$ 行 $W$ 列のグリッド状に並んだグリッドグラフを考えます。$i$ 行 $j$ 列目の頂点を $(i, j)$ と表すことにします。

グラフの辺の重みを定義するために、それぞれ $H-1, W, H, W-1$ 個の正の整数からなる、広義単調増加な4つの数列 $A, B, C, D$ を考えます。

• すべての $1 \le i \le H-1$ および $1 \le j \le W$ に対して、頂点 $(i, j)$ と $(i+1, j)$ を結ぶ重み $A_i + B_j$ の双方向辺が存在します。
• すべての $1 \le i \le H$ および $1 \le j \le W-1$ に対して、頂点 $(i, j)$ と $(i, j+1)$ を結ぶ重み $C_i + D_j$ の双方向辺が存在します。
• グラフにはこれら以外の辺は存在しません。

このグラフの最小全域木の辺の重みの総和を求めてください。

入力

入力の1行目には、2つの正の整数 $H$ と $W$ ($2 \le H, W \le 10^5$) が含まれます。 2行目には、数列 $A$ の要素である $H-1$ 個の整数 $A_i$ が含まれます。 3行目には、数列 $B$ の要素である $W$ 個の整数 $B_i$ が含まれます。 4行目には、数列 $C$ の要素である $H$ 個の整数 $C_i$ が含まれます。 5行目には、数列 $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