← 返回题目列表

AtCoder · awc0023_a

A. 厨师休息时间

中文机器翻译题面 查看原题

分数: 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