题目描述

给定长度为 $N$ 的整数序列 $A,B,C$。当且仅当满足以下条件时，すぬけ君会感到幸福：

• 对于所有整数 $x$，都有 $\sum\_{1 \leq i \leq N} |A\_i - x| \leq \sum\_{1 \leq i \leq N} |B\_i - x|$。

为了让すぬけ君幸福，你可以将 $A$ 的若干（可以为零）个元素修改为任意整数。将 $A_i$ 修改为 $t$ 的代价为 $C_i \times (A_i - t)^2$。修改后的值也必须是整数。

请你求出让すぬけ君幸福所需的最小总代价。

输入格式

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

$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

输出

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

输出

3758

样例 3

输入

1
0
0
1

输出

0

说明/提示

限制条件

• $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$
• 输入均为整数。

样例解释 1

可以按如下方式操作，总代价为 $6$：

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

操作后，$A = (2,1,3)$，此时すぬけ君感到幸福。

无法以低于 $6$ 的总代价达成目标，因此答案为 $6$。

由 ChatGPT 4.1 翻译