Problem Description

There are $ N $ red balls and $ N $ blue balls. The $ i $ -th red ball has an integer $ A_i $ written on it, and the $ i $ -th blue ball has an integer $ B_i $ written on it.

You can perform the following operation any number of times (between $ 0 $ and $ N $ times):

• Choose one red ball and one blue ball and eat them. In the $ i $ -th operation, if the integers written on the eaten balls are $ X $ and $ Y $ respectively, you gain $ XY + C_i $ points.

Find the maximum possible total score that can be obtained.

Input Format

The input is given from the standard input in the following format:

$ N $ $ A_1 $ $\ldots$ $ A_N $ $ B_1 $ $\ldots$ $ B_N $ $ C_1 $ $\ldots$ $ C_N $

Output Format

Output the maximum possible total score.

Sample Input and Output

Sample Input #1

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

Sample Output #1

79

Sample Input #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

Sample Output #2

6622583878238

Notes/Hints

Constraints

• All inputs are integers.
• $1 \le N \le 2 \times 10^5$
• $|A_i|, |B_i| \le 10^6$
• $1 \le C_i \le 10^{12}$

Partial Points

• If you solve the dataset where $1 \leq N \leq 1000$ correctly, you will be awarded $ 30 $ points.

Sample Explanation 1

$((-2) \times (-8) + 3) + (3 \times (-1) + 2) + (8 \times 7 + 5) = 79$ is the maximum possible total score.

见题面 Input 部分

见题面 Output 部分