103182: [Atcoder]ABC318 C - Blue Spring

Problem Statement

Takahashi is planning an $N$-day train trip.
For each day, he can pay the regular fare or use a one-day pass.

Here, for $1\leq i\leq N$, the regular fare for the $i$-th day of the trip is $F_i$ yen.
On the other hand, a batch of $D$ one-day passes is sold for $P$ yen. You can buy as many passes as you want, but only in units of $D$.
Each purchased pass can be used on any day, and it is fine to have some leftovers at the end of the trip.

Find the minimum possible total cost for the $N$-day trip, that is, the cost of purchasing one-day passes plus the total regular fare for the days not covered by one-day passes.

Constraints

• $1\leq N\leq 2\times 10^5$
• $1\leq D\leq 2\times 10^5$
• $1\leq P\leq 10^9$
• $1\leq F_i\leq 10^9$
• All input values are integers.

Input

The input is given from Standard Input in the following format:

$N$ $D$ $P$
$F_1$ $F_2$ $\ldots$ $F_N$

Output

Print the minimum possible total cost for the $N$-day trip.

Sample Input 1

5 2 10
7 1 6 3 6

Sample Output 1

20

If he buys just one batch of one-day passes and uses them for the first and third days, the total cost will be $(10\times 1)+(0+1+0+3+6)=20$, which is the minimum cost needed.
Thus, print $20$.

Sample Input 2

3 1 10
1 2 3

Sample Output 2

6

The minimum cost is achieved by paying the regular fare for all three days.

Sample Input 3

8 3 1000000000
1000000000 1000000000 1000000000 1000000000 1000000000 1000000000 1000000000 1000000000

Sample Output 3

3000000000

The minimum cost is achieved by buying three batches of one-day passes and using them for all eight days.
Note that the answer may not fit into a $32$-bit integer type.

问题描述

高桥正在计划一个 $N$ 天的火车旅行。

对于每一天，他可以选择支付普通票价或使用一日通。

其中，对于 $1\leq i\leq N$，旅行第 $i$ 天的普通票价是 $F_i$ 日元。

另一方面，一包 $D$ 张一日通售价为 $P$ 日元。你可以购买任意数量的通票，但必须以 $D$ 的倍数购买。

每购买的一张通票可以在任意一天使用，并且在旅行结束时剩下一些通票是没关系的。

找出 $N$ 天旅行的最低可能总成本，即购买一日通的费用加上没有一日通覆盖的那些天的普通票价总和。

限制条件

• $1\leq N\leq 2\times 10^5$
• $1\leq D\leq 2\times 10^5$
• $1\leq P\leq 10^9$
• $1\leq F_i\leq 10^9$
• 所有输入值都是整数。

输入

输入从标准输入中给出，如下所示：

$N$ $D$ $P$
$F_1$ $F_2$ $\ldots$ $F_N$

输出

打印 $N$ 天旅行的最低可能总成本。

样例输入 1

5 2 10
7 1 6 3 6

样例输出 1

20

如果他购买一包一日通并分别在第一天和第三天使用，总成本为 $(10\times 1)+(0+1+0+3+6)=20$，这是最低的需要成本。

因此，打印 $20$。

样例输入 2

3 1 10
1 2 3

样例输出 2

6

最低成本是在所有三天都支付普通票价的情况下实现的。

样例输入 3

8 3 1000000000
1000000000 1000000000 1000000000 1000000000 1000000000 1000000000 1000000000 1000000000

样例输出 3

3000000000

最低成本是在购买三包一日通并使用它们覆盖所有八天的情况下实现的。

注意答案可能无法容纳到一个 $32$ 位整数类型中。