AT_pakencamp_2023_day1_p MST (Hard)

長さ $ N $ の整数列 $ A,B $ が与えられます。 頂点 $ u $ と頂点 $ v $ を結ぶ辺の重みが $ A_u\times A_v + B_u \times B_v $ である完全グラフ $ G $ の最小全域木の重みを求めてください。

入力は以下の形式で標準入力から与えられる。 > $ N $ $ A_1 $ $ A_2 $ $ \ldots $ $ A_N $ $ B_1 $ $ B_2 $ $ \ldots $ $ B_N $

答えを出力せよ。

### Sample Explanation 1 頂点 $ 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 $ になります。 ### Sample Explanation 2 $ (A_i, B_i) = (A_j, B_j) $ となる $ i, j $ $ (i \neq j) $ が存在することもあります。 ### Constraints - $ 2 \leq N \leq 5\times 10^4 $ - $ |A_i|, |B_i| \le 10^6 $ - 入力は全て整数