注意事项

请在提交源代码前添加 #include "lawn.h"。

题目描述

在 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$ 行：$n\ c\ b$
• 第 $2$ 行：$a[0]\ a[1]\ \ldots\ a[n-1]$
• 第 $3$ 行：$v[0]\ v[1]\ \ldots\ v[n-1]$

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

样例 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 \leq n \leq 200000$
• 对于每个 $i$ $(0 \leq i < n)$，$1 \leq a[i] \leq 10^{9}$
• 对于每个 $i$ $(0 \leq i < n)$，$1 \leq v[i] \leq 10^{9}$
• $1 \leq b \leq 10^{9}$
• $1 \leq c \leq 10^{9}$
• 保证正确结果不超过 $10^{18}$

详细子任务附加限制及分值如下表所示。