在 Poenari 城堡的冒险之后，Vlad 回到了家。作为一个真正的罗马尼亚人，他的第一个想法就是应该喂他的马。这匹马对食物并不挑剔，因此 Vlad 决定将他的草坪作为马的主要食物来源。

为了完成这项任务，Vlad 有一台容量为 $c$ 的割草机。他决定将草坪分成 $n$ 条车道，编号为 $0$ 到 $n - 1$，他必须按此顺序依次修剪。每条车道 $i$ 含有数量为 $v[i]$ 的未剪杂草，并且由于某些未知原因，Vlad 推动割草机通过该车道需要花费 $a[i]$ 秒。

在经过几条车道后，割草机可能会达到满载容量，此时它会停止割草，并在该车道上留下一些未剪的草。每当发生这种情况时，它的集草袋就需要清空，这需要花费 $b$ 秒，且只能在车道的末端进行。如果集草袋在 Vlad 经过车道 $i$ 的过程中装满，他需要继续将割草机推到该车道的末端，清空集草袋，然后再次经过该车道一次（或根据需要经过多次），以剪掉剩余的草。例如，如果对于车道 $i$，我们必须通过它 $3$ 次才能清除所有的草，那么这将花费 $a[i] + b + a[i] + b + a[i]$ 秒。在修剪完整个草坪后，割草机必须被清空。

在经过长时间的思考和抱怨修剪完草坪需要花费太多时间后，Vlad 得出结论：有时在集草袋达到满载容量之前就将其清空可能会更省时间，但他不确定什么是最好的策略。因此，他向你寻求帮助。

给定每条车道上的草量、推动割草机通过每条车道所需的时间、集草袋的容量以及清空集草袋所需的时间，请帮 Vlad 找到在最短时间内完成草坪修剪的最佳方案。

实现细节

你需要实现以下函数：

long long mow(int n, int c, int b, std::vector<int> &a, std::vector<int> &v);

• $n$：草坪的车道数量
• $c$：集草袋的总容量
• $b$：清空集草袋所需的秒数
• $a$：长度为 $n$ 的数组，描述通过每条车道所需的时间
• $v$：长度为 $n$ 的数组，给出每条车道上的草量

该函数应返回一个整数，表示修剪完草坪所需的最小时间。

• 对于每个测试用例，该函数将被恰好调用一次。

数据范围

• $1 \le n \le 200\,000$
• $1 \le a[i] \le 10^9$（对于所有满足 $0 \le i < n$ 的 $i$）
• $1 \le v[i] \le 10^9$（对于所有满足 $0 \le i < n$ 的 $i$）
• $1 \le b \le 10^9$
• $1 \le c \le 10^9$
• 保证正确的结果最多为 $10^{18}$

子任务

1. （9 分）所有给定的值（$n, b, c, a[i]$ 和 $v[i]$）都最多为 $200$。
2. （16 分）$n, c \le 5000$ 且对于所有 $0 \le i < n$，有 $v[i] \le 5000$。
3. （36 分）$c \le 200\,000$。
4. （17 分）$a[0] = a[1] = \dots = a[n - 1]$。
5. （22 分）无附加限制。

样例

样例 1

考虑以下调用：

mow(3, 5, 2, {2, 10, 3}, {2, 4, 6})

在这个样例中，有 $3$ 条车道，集草袋的容量为 $5$，清空它需要 $2$ 秒。

对于这个样例，Vlad 将在 $2$ 秒内修剪第一条车道。割草机中的草量将为 $2$。然后他将在 $2$ 秒内清空割草机。在第一条车道上，他花费了 $4$ 秒。

接着他将通过第二条车道。他将割掉 $4$ 单位的草。在修剪完第二条车道后，他选择不清空集草袋。在第二条车道上花费的时间是 $10$ 秒。

对于第三条车道，他开始修剪。在割掉 $1$ 单位的草后，他的割草机装满了，因此他必须走到该车道的末端，清空割草机，然后再次开始修剪第三条车道。请记住，在整个草坪修剪完毕后，割草机必须被清空。在第三条车道上花费的时间是 $3 + 2 + 3 + 2 = 10$ 秒。

总共，他花费了 $4 + 10 + 10 = 24$ 秒。可以证明这是 Vlad 修剪草坪的最优策略。

样例 2

考虑以下调用：

mow(4, 10, 4, {1, 2, 1, 4}, {3, 2, 6, 7})

在这个样例中，有 $4$ 条车道，集草袋的容量为 $10$，清空它需要 $4$ 秒。

最优策略是直接通过前 $3$ 条车道，之后集草袋将被装满，剩余的草量数组将为 $[0, 0, 1, 7]$。此后，应该清空集草袋，然后修剪最后 $2$ 条车道，并在最后再次清空集草袋。

总秒数将为 $a[0] + a[1] + a[2] + b + a[2] + a[3] + b = 17$。

评测程序示例

样例评测程序按以下格式读取输入：

• 第 1 行：$n \ c \ b$
• 第 2 行：$a[0] \ a[1] \ \dots \ a[n - 1]$
• 第 3 行：$v[0] \ v[1] \ \dots \ v[n - 1]$

并输出使用相应参数调用 mow 的结果。