题目描述

数据中心需要在接下来的 $n$ 个时段内完成一系列计算任务，因此必须提前规划购电方案，以尽可能降低总成本。

具体来说，第 $i$ 个时段需要消耗 $w_i$ 单位电量，并且这部分电量必须在第 $i$ 个时段结束前全部准备好。为此，你可以在任意时段购买电量：如果在第 $i$ 个时段购电，那么每单位电量的价格为 $c_i$ 元。

然而，不同时段的电价可能存在明显差异。为了更好地利用这一点，数据中心配备了一块容量为 $k$ 的储能电池。借助这块电池，你可以在电价较低的时段多买一些电先存起来，再在后续电价较高或需要用电的时段从电池中取出使用，从而减少整体支出。

电池的初始电量为 $0$，充电和放电过程中的损耗可以忽略不计；同时，在任何时刻，电池中的电量都不能超过容量 $k$，也不能低于 $0$。

现在请你计算，在保证所有时段用电需求都能够被满足的前提下，最少需要花费多少元购电。

输入格式

输入共 3 行。

第一行包含两个整数 $n$ 和 $k$，分别表示时段数量和储能电池的容量。

第二行包含 $n$ 个非负整数 $w_1, w_2, \dots, w_n$，其中 $w_i$ 表示第 $i$ 个时段所需的电量。

第三行包含 $n$ 个非负整数 $c_1, c_2, \dots, c_n$，其中 $c_i$ 表示第 $i$ 个时段购买单位电量的价格。

输出格式

输出一行，一个非负整数，表示满足所有时段用电需求所需的最小购电成本。

3 1
1 2 1
20 25 100

90

提示

【样例说明】

最优方案如下：

• 第 $1$ 个时段购买 $2$ 单位电量，花费 $2 \times 20 = 40$ 元；其中 $1$ 单位立即使用，另外 $1$ 单位存入电池；
• 第 $2$ 个时段购买 $2$ 单位电量，花费 $2 \times 25 = 50$ 元；这 $2$ 单位电量全部用于当前时段的需求；
• 第 $3$ 个时段直接使用电池中剩余的 $1$ 单位电量，无需额外购电。

因此，总花费为 $40 + 50 = 90$ 元。

【评测用例规模与约定】

对于 $20\%$ 的数据，$n \leq 10$，$k \leq 10$；

对于 $40\%$ 的数据，$n \leq 500$，$k \leq 1000$；

对于另 $20\%$ 的数据，$n \leq 3000$，且 $\sum w_i \leq 10^6$；

对于另 $10\%$ 的数据，$k \leq 100$；

对于 $100\%$ 的数据，$1 \leq n \leq 5 \times 10^5$，$0 \leq k \leq 10^9$，$0 \leq w_i, c_i \leq 10^9$。