LR Minimum Spanning Tree

問題文

正整数 $N$ と長さ $N$ の正整数列 $L=(L_1,L_2,\dots,L_N)$, $R=(R_1,R_2,\dots,R_N)$ が与えられる。

$N$ 頂点の重み付き完全無向グラフがある。各頂点には $1,2,\dots,N$ の番号が振られており、頂点 $i,j$ $(i<j)$ を結ぶ辺の重みは $L_i+R_j$ である。

このグラフの最小全域木の重みを求めよ。

制約

• 入力はすべて整数である。
• $2 \le N \le 2\times 10^5$
• $1 \le L_i,R_i \le 10^9$ $(1\le i\le N)$

入力

入力は以下の形式で標準入力から与えられる。

出力

答えを出力せよ。

サンプル

サンプル 1

入力

5
6 2 9 1 5
4 7 3 8 2

出力

20