/ 
実行時間制限: 5 sec / メモリ制限: 1024 MB
配点 : 2400 点
問題文
長さ 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 の要素を 0 個以上変更することにしました． A_i を t に変更するには，C_i \times (A_i-t)^2 のコストがかかります． 変更後の値も整数でなければなりません．
すぬけくんが幸せになるためにかかるコストの合計の最小値を求めてください．
制約
- 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) となりますが，このときすぬけくんは幸せです． 合計コスト 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
Score : 2400 points
Problem Statement
Integer sequences A, B and C, each of length N, are given. Snuke is happy if and only if the following condition is met.
- For every integer x, \sum_{1 \leq i \leq N} |A_i-x| \leq \sum_{1 \leq i \leq N} |B_i-x| holds.
He decided to change at least 0 elements of A to become happy. It costs him C_i \times (A_i-t)^2 to change A_i to t. Here, t, the value after the change, should be an integer as well.
Find the minimum possible sum of costs in order for Snuke to become happy.
Constraints
- 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
- All values in input are integers.
Input
Input is given from Standard Input in the following format:
N A_1 A_2 \cdots A_N B_1 B_2 \cdots B_N C_1 C_2 \cdots C_N
Output
Print the answer.
Sample Input 1
3 0 1 4 1 2 3 1 3 2
Sample Output 1
6
After the following operations, the sum of costs is 6.
- Change A_1 to 2. This change costs 1 \times (0-2)^2=4.
- Change A_3 to 3. This change costs 2 \times (4-3)^2=2.
After the operations, A=(2,1,3) holds, which makes Snuke happy. It is impossible to achieve the goal with sum of costs less than 6, so the answer is 6.
Sample Input 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
Sample Output 2
3758
Sample Input 3
1 0 0 1
Sample Output 3
0