题目描述

小 X 和小 J 各有一个长度为 $N$ 的整数序列。小 X 的序列为 $A_1, A_2, \dots, A_N$，小 J 的序列为 $B_1, B_2, \dots, B_N$。此外，还有一个代价系数序列 $C_1, C_2, \dots, C_N$。

小 X 希望修改自己的序列 $A$（可以将任意多个元素修改为任意整数），使得对于每一个整数 $x$，都有

$$\sum_{i=1}^N |A_i - x| \;\leq\; \sum_{i=1}^N |B_i - x|.$$

如果这个条件成立，小 X 就会感到幸福。

将 $A_i$ 修改为 $t$ 的代价为 $C_i \times (A_i - t)^2$。修改后的值也必须为整数。小 X 想知道，为了让自己幸福，最少需要支付多少总代价。

请你帮助小 X 计算这个最小代价。

输入格式

第一行一个整数 $N$。

第二行 $N$ 个整数 $A_1, A_2, \dots, A_N$。

第三行 $N$ 个整数 $B_1, B_2, \dots, B_N$。

第四行 $N$ 个整数 $C_1, C_2, \dots, C_N$。

输出格式

输出一个整数，表示最小总代价。

输入输出样例

输入 #1

3
0 1 4
1 2 3
1 3 2

输出 #1

6

输入 #2

20
185 89 216 105 56 383 193 161 75 196 322 180 390 15 206 78 275 338 225 167
161 77 294 117 22 382 218 140 57 231 343 160 397 8 264 68 301 349 295 157
3 1 3 5 2 1 3 4 1 4 2 2 2 2 5 1 1 5 4 3

输出 #2

3758

输入 #3

1
0
0
1

输出 #3

0

样例解释 #1

可以按如下方式修改：

• 将 $A_1$ 改为 $2$，代价为 $1 \times (0-2)^2 = 4$。
• 将 $A_3$ 改为 $3$，代价为 $2 \times (4-3)^2 = 2$。

修改后 $A = (2,1,3)$，此时条件成立。总代价为 $6$，且无法更小。

数据范围

对于 100% 的数据，满足 $1 \leq N \leq 2 \times 10^5$，$0 \leq A_i, B_i \leq 2 \times 10^5$，$1 \leq C_i \leq 10^9$。

• Subtask 1（20pts）$n\le 5,A_i,B_i,C_i\le 5$
• Subtask 2（20pts）$C_i=1$
• Subtask 3（40pts）$C_i\le 5$
• Subtask 4（20pts）无特殊限制