配点 : {100} 点
問題文
红球和蓝球各 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 点。 如果您正确回答了所有满足
入力
输入是按以下格式从标准输入给出的。
N A_1 \ldots A_N B_1 \ldots B_N C_1 \ldots C_N
出力
输出可获得的总分最大值。
入力例 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