問題文

長さ N の整数列 A,B が与えられます。

頂点 u と頂点 v を結ぶ辺の重みが A_u\times A_v + B_u \times B_v である完全グラフ G の最小全域木の重みを求めてください。

制約

• 2 \leq N \leq 5\times 10^4
• |A_i|, |B_i| \le 10^6
• 入力は全て整数

入力例 1

3
1 3 -1
-2 0 -4

出力例 1

0

頂点 1 と頂点 2 を結ぶ辺の重みは 1 \times 3 + (-2) \times 0 = 3 、

頂点 1 と頂点 3 を結ぶ辺の重みは 1 \times (-1) + (-2) \times (-4) = 7 、

頂点 2 と頂点 3 を結ぶ辺の重みは 3 \times (-1) + 0 \times (-4) = -3 です。

よって 1 と 2 を結ぶ辺と 2 と 3 を結ぶ辺で全域木を作るのが最小で、この木の重みは 0 になります。

入力例 2

4
1 1 -1 -1
1 1 -1 -1

出力例 2

-6

(A_i, B_i) = (A_j, B_j) となる i, j (i \neq j) が存在することもあります。

入力例 3

10
-593389 -914534 -534565 -257272 -723595 763395 -272810 -869922 449729 -111959
743146 -30912 -528945 903153 -162840 -807868 227877 -433864 751438 34288

出力例 3

-5395522482698