题目描述

给定长度为$N$的整数序列$A, B$和$C$。只有满足以下条件时，Snuke才会感到幸福：

• 对于每个整数$x$，有$\\sum_{1 \\leq i \\leq N} |A_i-x| \\leq \\sum_{1 \\leq i \\leq N} |B_i-x|$。

他决定改变至少$0$个$A$的元素以获得幸福。将$A_i$改变为$t$需要花费他$C_i \\times (A_i-t)^2$。这里，改变后的值$t$也必须是整数。

找到使Snuke感到幸福所需的最小总花费。

约束条件

• $1 \leq N \leq 2 \times 10^5$
• $0 \leq A_i \leq 2 \times 10^5$
• $0 \leq B_i \leq 2 \times 10^5$
• $1 \leq C_i \leq 5$
• 输入中的所有值都是整数。

输入

输入以以下格式从标准输入给出：

$N$

$A_1$ $A_2$ $\cdots$ $A_N$

$B_1$ $B_2$ $\cdots$ $B_N$

$C_1$ $C_2$ $\cdots$ $C_N$

输出

输出答案。

示例输入1

3
0 1 4
1 2 3
1 3 2

示例输出1

6

执行以下操作后，总花费为$6$。

• 将$A_1$改为$2$。此次改变花费为$1 \times (0-2)^2=4$。
• 将$A_3$改为$3$。此次改变花费为$2 \times (4-3)^2=2$。

经过这些操作，有$A=(2,1,3)$，满足Snuke的要求。无法使总花费小于$6$实现目标，因此答案是$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