A - 本棚の整理 解説 /

実行時間制限: 2 sec / メモリ制限: 1024 MiB

配点 : 233 点

問題文

高橋君は図書館で本棚の整理をするアルバイトをしています。

本棚には N 冊の本を一列に並べる必要があります。各本には 1 から N の固有の番号が付けられており、本 i の厚さは D_i センチメートルです。

本棚の左端にはブックエンド（幅 S センチメートル）が固定されています。N 冊の本はすべて、このブックエンドの右側に左から右へ一列に並べます。本棚の右端には制限はなく、十分な長さがあるものとします。

図書館の規則では、本の傷みを防ぐため、隣り合う本同士の間には少なくとも K センチメートルの間隔を空ける必要があります。また、ブックエンドと最も左の本との間にも K センチメートル以上の間隔を空ける必要があります。ここで、2つの物の間の間隔とは、左側の物の右端から右側の物の左端までの距離を指します。

高橋君は、N 冊の本すべてをちょうど1回ずつ、好きな順番で並べることができます。すべての本を並べ終えたとき、ブックエンドの左端から最も右の本の右端までの距離の最小値を求めてください。

制約

  • 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
  • 1 行目には、本の冊数を表す整数 N 、ブックエンドの幅を表す整数 S 、必要な最小間隔を表す整数 K が、スペース区切りで与えられる。
  • 2 行目には、各本の厚さを表す整数 D_1, D_2, \ldots, D_N が、スペース区切りで与えられる。

出力

ブックエンドの左端から最も右の本の右端までの距離の最小値を整数で 1 行に出力してください。

入力例 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

Score : 233 pts

Problem Statement

Takahashi has a part-time job organizing bookshelves at a library.

He needs to arrange N books in a row on a bookshelf. Each book has a unique number from 1 to N, and book i has a thickness of D_i centimeters.

A bookend (with width S centimeters) is fixed at the left end of the bookshelf. All N books are to be placed in a row from left to right, to the right of this bookend. There is no restriction on the right end of the bookshelf, and it can be assumed to be sufficiently long.

According to the library's rules, to prevent damage to the books, there must be a gap of at least K centimeters between any two adjacent books. Additionally, there must be a gap of at least K centimeters between the bookend and the leftmost book. Here, the gap between two objects refers to the distance from the right edge of the left object to the left edge of the right object.

Takahashi can arrange all N books exactly once each, in any order he likes. After all books have been placed, find the minimum possible distance from the left edge of the bookend to the right edge of the rightmost book.

Constraints

  • 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)
  • All inputs are integers

Input

N S K
D_1 D_2 \cdots D_N
  • The first line contains three space-separated integers: N representing the number of books, S representing the width of the bookend, and K representing the required minimum gap.
  • The second line contains space-separated integers D_1, D_2, \ldots, D_N representing the thickness of each book.

Output

Print the minimum possible distance from the left edge of the bookend to the right edge of the rightmost book as an integer on a single line.

Sample Input 1

3 2 1
3 1 2

Sample Output 1

11

Sample Input 2

1 5 3
4

Sample Output 2

12

Sample Input 3

5 1000000000 1000000000
1000000000 1000000000 1000000000 1000000000 1000000000

Sample Output 3

11000000000