/ 
Time Limit: 2 sec / Memory Limit: 1024 MB
配点 : 300 点
問題文
高橋君は N 日間の鉄道旅行を計画しています。
高橋君はそれぞれの日について、運賃の通常料金を払うか、1 日周遊パスを 1 枚使用するか選ぶことができます。
ここで、1\leq i\leq N について、i 日目の旅行にかかる運賃の通常料金は F_i 円です。
一方、1 日周遊パスは D 枚セットで P 円で発売されており、何セットでも購入することが可能ですが、D 枚単位でしか購入することができません。
また、購入したパスは 1 枚ずつ好きな日に使うことができ、旅行が終了した時点で余っていても構いません。
N 日間の旅行でかかる金額、すなわち 1 日周遊パスの購入にかかった代金と、1 日周遊パスを利用しなかった日における運賃の通常料金の合計金額の和としてあり得る最小値を求めてください。
制約
- 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
1 日周遊パスを 1 セットだけ購入し、1 日目と 3 日目に使用すると、合計金額は (10\times 1)+(0+1+0+3+6)=20 となり、このときかかる金額が最小となります。
よって、20 を出力します。
入力例 2
3 1 10 1 2 3
出力例 2
6
3 日間すべてにおいて運賃の通常料金を支払ったときに最小となります。
入力例 3
8 3 1000000000 1000000000 1000000000 1000000000 1000000000 1000000000 1000000000 1000000000 1000000000
出力例 3
3000000000
1 日周遊パスを 3 セット購入し、8 日間すべてにおいて 1 日周遊パスを利用したときに最小となります。
答えが 32 bit 整数型に収まらないことがあることに注意してください。
Score : 300 points
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.