問題文

赤いボールと青いボールがそれぞれ N 個あります。i 個目の赤いボールには整数 A_i が、i 個目の青いボールには整数 B_i が書かれています。

あなたは次の操作を 0 回以上 N 回以下の好きな回数行えます。

• 赤いボールと青いボールを 1 個ずつ選び、食べる。i 回目の操作では、食べたボールに書かれていた整数がそれぞれ X, Y であるとして、XY + C_i 点を得る。

獲得可能な合計点数の最大値を求めてください。

制約

• 入力は全て整数
• 1 \le N \le 2 \times 10^5
• |A_i|, |B_i| \le 10^6
• 1 \le C_i \le 10^{12}

部分点

• 1 \leq N \leq 1000 を満たすデータセットに正解した場合は 30 点が与えられる。

入力例 1

4
6 -2 3 8
-1 -1 7 -8
3 2 5 4

出力例 1

79

((-2) \times (-8) + 3) + (3 \times (-1) + 2) + (8 \times 7 + 5) = 79 点が獲得可能な合計点数の最大値です。

入力例 2

10
-809372 563575 -351229 -20556 -309920 85426 -952799 739479 -66554 -296504
735902 631932 -407775 895728 302156 -968417 -963982 -894325 -804784 78537
282707723857 731189330739 1910286918 339802329211 611404539679 296303238506 337317063340 503492686568 1614407806 11314313

出力例 2

6622583878238