时空限制

1S/512M

题目描述

给定两个长度为 $n$ 的整数数组 $a$ 和 $b$。定义这两个数组的“积”为：

$$\sum_{i = 1}^{n} a_i \times b_i = a_1 b_1 + a_2 b_2 + \cdots + a_n b_n $$

你可以对数组 $a$ 执行以下两种操作，且总操作次数至多为 $m$ 次：

• 选择一个下标 $i$（$1 \le i \le n$），使 $a_1, a_2, \ldots, a_i$ 的值同时加 $1$。
• 选择一个下标 $i$（$1 \le i \le n$），使 $a_1, a_2, \ldots, a_i$ 的值同时减 $1$。

同时，给你一个长度为 $n$ 的数组 $c$，对于每个下标 $i$，将其选作操作对象（无论加还是减）的总次数不能超过 $c_i$ 次。

请计算经过至多 $m$ 次操作后，这两个数组的“积”可能达到的最大值。

格式

输入格式

第一行包含两个整数 $n$ 和 $m$，分别表示数组的长度以及最多允许的操作总次数。

第二行包含 $n$ 个整数 $a_1, a_2, \ldots, a_n$，表示数组 $a$ 的初始元素。

第三行包含 $n$ 个整数 $b_1, b_2, \ldots, b_n$，表示数组 $b$ 的元素。

第四行包含 $n$ 个整数 $c_1, c_2, \ldots, c_n$，表示对每个下标操作次数的上限。

输出格式

输出一行一个整数，表示在满足所有条件的情况下，两数组最大的积。

样例

样例输入 #1

3 3
0 0 0
1 2 -4
2 2 2

样例输出 #1

7

样例解释 #1

初始状态下，两个数组的积为 $0 \times 1 + 0 \times 2 + 0 \times (-4) = 0$。

为了使积最大化，我们可以做如下操作：

• 第 $1$ 次操作：选择下标 $i=2$，执行加 $1$ 操作。数组 $a$ 变为 [1, 1, 0]。
• 第 $2$ 次操作：选择下标 $i=2$，执行加 $1$ 操作。数组 $a$ 变为 [2, 2, 0]。此时下标 $2$ 的操作次数达到限制 $c_2=2$。
• 第 $3$ 次操作：选择下标 $i=3$，执行减 $1$ 操作。数组 $a$ 变为 [1, 1, -1]。

操作结束后，两数组的积为 $1 \times 1 + 1 \times 2 + (-1) \times (-4) = 1 + 2 + 4 = 7$。这也是可以得到的最大积。

数据规模

注意：你只有通过了子任务的所有测试点，才能获得对应子任务的分数。

子任务编号	分数	$n\le$
$1$	$40$	$2000$
$2$	$60$	$2\times 10^5$

对于 $100\%$ 的数据，$1 \leq n \leq 2 \times 10^5$，$0 \leq m \leq 10^9$，$-10^4 \leq a_i, b_i \leq 10^4$，$0 \leq c_i \leq 10^4$。