Score : $300$ points

问题描述

高桥正在计划一次 $N$ 天的火车旅行。
对于每一天，他可以选择支付正常票价或者使用一日通票。

这里，对于 $1\leq i\leq N$，旅行第 $i$ 天的正常票价为 $F_i$ 日元。
另一方面，一组包含 $D$ 张的一日通票售价为 $P$ 日元。你可以任意购买通票，但必须按 $D$ 的整数倍购买。
每张购买的通票可以在任何一天使用，并且在旅行结束时剩余一些通票也是可以接受的。

请你找出 $N$ 天旅行所需的最小总花费，即购买一日通票的费用加上未被一日通票覆盖的天数的正常票价之和。

以上为通义千问 qwen-max 翻译，仅供参考。

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.

update @ 2024/3/10 09:04:30