C - Cost to Flip Editorial /

Time Limit: 2 sec / Memory Limit: 1024 MiB

配点 : 600 点

問題文

0 と 1 のみからなる 2 つの長さ N の整数列 A = (A_1, A_2, \ldots, A_N) と B = (B_1, B_2, \ldots, B_N) が与えられます。

A に対して下記の操作を好きな回数（ 0 回でも良い）だけ行うことができます。

  1. まず、1 \leq i \leq N を満たす整数 i を選び、A_i の値を反転する（元の値が 0 ならば 1 に、元の値が 1 ならば 0 に変更する）。
  2. その後、操作のコストとして、\sum_{k=1}^N A_kC_k 円を支払う。

上記の手順 2. におけるコストの計算には、手順 1. で変更が加えられた後の A を用いることに注意してください。

A を B に一致させるために支払う合計費用の最小値を出力してください。

制約

  • 1 \leq N \leq 2 \times 10^5
  • A_i, B_i \in \lbrace 0, 1\rbrace
  • 1 \leq C_i \leq 10^6
  • 入力はすべて整数

入力

入力は以下の形式で標準入力から与えられる。

N
A_1 A_2 \ldots A_N
B_1 B_2 \ldots B_N
C_1 C_2 \ldots C_N

出力

答えを出力せよ。

入力例 1

4
0 1 1 1
1 0 1 0
4 6 2 9

出力例 1

16

下記の手順を考えます。

  • まず A_4 を反転する。その結果、A = (0, 1, 1, 0) となる。この操作のコストとして 0 \times 4 + 1 \times 6 + 1 \times 2 + 0 \times 9 = 8 円支払う。
  • 次に A_2 を反転する。その結果、A = (0, 0, 1, 0) となる。この操作のコストとして 0 \times 4 + 0 \times 6 + 1 \times 2 + 0 \times 9 = 2 円支払う。
  • 最後に A_1 を反転する。その結果、A = (1, 0, 1, 0) となり、B に一致する。この操作のコストとして 1 \times 4 + 0 \times 6 + 1 \times 2 + 0 \times 9 = 6 円支払う。

このとき、支払う合計費用は 8 + 2 + 6 = 16 円であり、これが考えられる最小値です。

入力例 2

5
1 1 1 1 1
1 1 1 1 1
1 1 1 1 1

出力例 2

0

A と B ははじめから一致しているため、一度も操作を行う必要がありません。

入力例 3

20
1 1 1 1 0 0 1 1 0 0 0 1 0 1 0 1 1 0 1 0
0 0 0 1 1 1 0 1 1 0 0 0 0 0 0 1 0 1 0 0
52 73 97 72 54 15 79 67 13 55 65 22 36 90 84 46 1 2 27 8

出力例 3

2867

Score : 600 points

Problem Statement

You are given two integer sequences of length N, A = (A_1, A_2, \ldots, A_N) and B = (B_1, B_2, \ldots, B_N), each consisting of 0 and 1.

You can perform the following operation on A any number of times (possibly zero):

  1. First, choose an integer i satisfying 1 \leq i \leq N, and flip the value of A_i (if the original value is 0, change it to 1; if it is 1, change it to 0).
  2. Then, pay \sum_{k=1}^N A_k C_k yen as the cost of this operation.

Note that the cost calculation in step 2 uses the A after the change in step 1.

Print the minimum total cost required to make A identical to B.

Constraints

  • 1 \leq N \leq 2 \times 10^5
  • A_i, B_i \in {0, 1}
  • 1 \leq C_i \leq 10^6
  • All input values are integers.

Input

The input is given from Standard Input in the following format:

N
A_1 A_2 \ldots A_N
B_1 B_2 \ldots B_N
C_1 C_2 \ldots C_N

Output

Print the answer.

Sample Input 1

4
0 1 1 1
1 0 1 0
4 6 2 9

Sample Output 1

16

Consider the following procedure:

  • First, flip A_4. Now, A = (0, 1, 1, 0). The cost of this operation is 0 \times 4 + 1 \times 6 + 1 \times 2 + 0 \times 9 = 8 yen.
  • Next, flip A_2. Now, A = (0, 0, 1, 0). The cost of this operation is 0 \times 4 + 0 \times 6 + 1 \times 2 + 0 \times 9 = 2 yen.
  • Finally, flip A_1. Now, A = (1, 0, 1, 0), which matches B. The cost of this operation is 1 \times 4 + 0 \times 6 + 1 \times 2 + 0 \times 9 = 6 yen.

In this case, the total cost is 8 + 2 + 6 = 16 yen, which is the minimum possible.

Sample Input 2

5
1 1 1 1 1
1 1 1 1 1
1 1 1 1 1

Sample Output 2

0

A and B are already identical initially, so there is no need to perform any operations.

Sample Input 3

20
1 1 1 1 0 0 1 1 0 0 0 1 0 1 0 1 1 0 1 0
0 0 0 1 1 1 0 1 1 0 0 0 0 0 0 1 0 1 0 0
52 73 97 72 54 15 79 67 13 55 65 22 36 90 84 46 1 2 27 8

Sample Output 3

2867