分数: 300 点
问题陈述
高桥正在计划 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- 位整数类型。