该比赛已结束，您无法在比赛模式下递交该题目。您可以点击“在题库中打开”以普通模式查看和递交本题。

翻转费用

题目描述

给定两个仅由 $0$ 和 $1$ 组成的长度为 $N$ 的整数序列 $A = (A_1, A_2, \ldots, A_N)$ 和 $B = (B_1, B_2, \ldots, B_N)$，以及一个长度为 $N$ 的正整数序列 $C = (C_1, C_2, \ldots, C_N)$。

你可以对 $A$ 执行任意次（包括 0 次）以下操作，目标是将 $A$ 变为 $B$，并求出所需支付的最小总成本：

1. 反转操作：选择一个整数 $i$（$1 \leq i \leq N$），将 $A_i$ 的值反转（0 变 1，1 变 0）；
2. 成本支付：每次操作后，需支付的成本为当前序列 $A$ 中所有元素与对应 $C_i$ 的乘积之和，即 $\sum_{k=1}^N A_k C_k$。

输入格式

第一行输入整数 $N$； 第二行输入序列 $A$ 的 $N$ 个元素 $A_1\ A_2\ \ldots\ A_N$； 第三行输入序列 $B$ 的 $N$ 个元素 $B_1\ B_2\ \ldots\ B_N$； 第四行输入序列 $C$ 的 $N$ 个元素 $C_1\ C_2\ \ldots\ C_N$。

输出格式

输出将 $A$ 变为 $B$ 所需的最小总成本。

样例

样例输入 1

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

样例输出 1

16

样例解释 1

通过以下操作序列达成目标，总成本为 $16$：

1. 反转 $A_4$，此时 $A = (0, 1, 1, 0)$，支付成本 $0 \times 4 + 1 \times 6 + 1 \times 2 + 0 \times 9 = 8$；
2. 反转 $A_2$，此时 $A = (0, 0, 1, 0)$，支付成本 $0 \times 4 + 0 \times 6 + 1 \times 2 + 0 \times 9 = 2$；
3. 反转 $A_1$，此时 $A = (1, 0, 1, 0)$（与 $B$ 一致），支付成本 $1 \times 4 + 0 \times 6 + 1 \times 2 + 0 \times 9 = 6$。

样例输入 2

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

样例输出 2

0

样例解释 2

初始时 $A$ 已与 $B$ 完全一致，无需执行任何操作，成本为 $0$。

样例输入 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

数据范围

• $1 \leq N \leq 2 \times 10^5$
• $A_i, B_i \in \{0, 1\}$（序列 $A$、$B$ 仅含 0 和 1）
• $1 \leq C_i \leq 10^6$（序列 $C$ 为正整数）
• 所有输入值均为整数

提示

• 树状数组
• 前缀和
• 贪心
• 二分

子任务