Description

在经历了 Poenari 城堡的冒险之后，Vlad 回到家，作为一个真正的罗马尼亚人，他的第一想法就是应该先喂他的马。马对食物要求不高，所以 Vlad 直接把自家草坪当作主要饲料来源。

为此，Vlad 有一台容量为 $c$ 的割草机。他决定将草坪划分为 $n$ 条割草道，编号从 $0$ 到 $n - 1$，并且必须按顺序割完。第 $i$ 条割草道上有 $v[i]$ 数量的未割草，由于一些未知原因，Vlad 推割草机经过这一条需要 $a[i]$ 秒。

在经过几条割草道后，割草机的收集箱可能会达到满容量，此时它将停止割草，剩下的草会留在该条道上。每当出现这种情况时，必须在该条道的末端清空收集箱，这需要花费 $b$ 秒。清空只能在割草道的末端进行。如果在经过第 $i$ 条割草道时收集箱已满，Vlad 仍需要推到该条道的末端，再清空收集箱，然后重新经过该条道一次（或多次），直到割完剩余的草。

例如，如果某条第 $i$ 条割草道需要经过 $3$ 次才能割完全部草，则所需时间为：

在整个草坪割完后，割草机也必须清空一次。

经过一番思考并抱怨说割完需要花费太久，Vlad 得出结论：有时候提前清空收集箱（即便还没满）可能会更节省时间，但他不确定最佳策略。因此他请求你的帮助。

给定每条割草道上的草量、经过该条所需的时间、收集箱容量以及清空所需的时间，求 Vlad 在最短时间内完成割草的最佳策略所需的总时间。

Input Format

实现细节

你需要实现以下过程：

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

• $n$：草坪的割草道数量
• $c$：收集箱的总容量
• $b$：清空收集箱所需的秒数
• $a$：长度为 $n$ 的数组，表示经过每条割草道所需的时间
• $v$：长度为 $n$ 的数组，表示每条割草道上的草量

该过程应返回一个整数，表示完成割草的最短时间。

该过程在每个测试用例中恰好调用一次。

3 5 2
2 10 3
2 4 6

24

4 10 4
1 2 1 4
3 2 6 7

17

Hint

样例解释 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$ 秒）。第三条道总用时 $3 + 2 + 3 + 2 = 10$ 秒。

总用时 $4 + 10 + 10 = 24$ 秒。可以证明这是 Vlad 割草的最优策略。

数据范围

• $1 \leq n \leq 200000$
• 对于每个 $0 \leq i < n$，$1 \leq a[i] \leq 10^9$
• 对于每个 $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}$。

子任务

1. （9 分）所有给定值（$n$、$b$、$c$、$a[i]$、$v[i]$）均不超过 $200$
2. （16 分）$n, c \leq 5000$ 且对所有 $0 \leq i < n$，$v[i] \leq 5000$
3. （36 分）$c \leq 200000$
4. （17 分）$a[0] = a[1] = \ldots = a[n - 1]$
5. （22 分）无额外限制

翻译由 ChatGPT-5 完成