← 返回题目列表

AtCoder · utpc2021_c

C. 产品搭配

中文机器翻译题面 查看原题

配点 : {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