分数: 233 分
问题陈述
高桥在图书馆有一份整理书架的兼职工作。
他需要安排 N 书架上一排书。每本书都有一个唯一的编号 1 to N,并预订 i 的厚度为 D_i 厘米。
书挡(宽度 S 厘米)固定在书架的左端。全部 N 书籍应从左到右排成一排,放置在书挡的右侧。书架右端没有限制,可以假设足够长。
根据图书馆的规定,为防止图书损坏,图书之间的间隙必须至少为 任意两本相邻书籍之间的 K 厘米。此外,必须有至少一个间隙 K 书挡和最左边的书之间的厘米。这里,两个对象之间的间隙是指从左对象的右边缘到右对象的左边缘的距离。
高桥可以安排一切 N 每人只预订一次,按照他喜欢的任何顺序。放置完所有书籍后,求从书挡的左边缘到最右边的书的右边缘的最小可能距离。
约束
- 1 \leq N \leq 10^5
- 1 \leq S \leq 10^9
- 1 \leq K \leq 10^9
- 1 \leq D_i \leq 10^9 (1 \leq i \leq N)
- 所有输入均为整数
输入
N S K D_1 D_2 \cdots D_N
- 第一行包含三个空格分隔的整数: N 代表图书数量, S 代表书挡的宽度,以及 K 代表所需的最小间隙。
- 第二行包含空格分隔的整数 D_1, D_2, \ldots, D_N 代表每本书的厚度。
输出
在一行上以整数形式打印从书挡的左边缘到最右边的书的右边缘的最小可能距离。
示例输入 1
3 2 1 3 1 2
示例输出 1
11
示例输入 2
1 5 3 4
示例输出 2
12
示例输入 3
5 1000000000 1000000000 1000000000 1000000000 1000000000 1000000000 1000000000
示例输出 3
11000000000