分数: 200 分
问题陈述
高桥是一名在餐厅厨房工作的厨师。
今天,高桥需要做好准备 N 成分。准备材料所需的时间 i第一种成分是 T_i 秒。高桥一次只能准备一种食材。
另外,根据厨房规则,高桥必须准确地拿走 M 工作期间休息。每次休息需要 R 秒。只能在完成任何配料后立即休息(在开始第一个配料之前或完成最后一个配料后不能休息)。
准备好所有原料并准确取出时,求从开始工作到完成所有工作的最短总时间 M 中断。请注意,可以自由选择准备成分的顺序。
约束
- 2 \leq N \leq 2 \times 10^5
- 1 \leq M \leq N - 1
- 1 \leq R \leq 10^9
- 1 \leq T_i \leq 10^9 (1 \leq i \leq N)
- 所有输入均为整数
输入
N M R T_1 T_2 \ldots T_N
- 第一行包含 N 代表成分数量, M 代表中断次数,以及 R 代表一次休息的时间,以空格分隔。
- 第二行包含时间 T_1, T_2, \ldots, T_N 需要准备每种成分,用空格分隔。
输出
一行输出准备所有原料并准确取用的最短总时间 M 中断。
示例输入 1
3 1 5 10 20 30
示例输出 1
65
示例输入 2
5 2 10 3 7 2 8 5
示例输出 2
45
示例输入 3
10 4 1000000000 100 200 300 400 500 600 700 800 900 1000
示例输出 3
4000005500