A - Growing Slime Editorial /

Time Limit: 2 sec / Memory Limit: 1024 MiB

配点 : 233 点

問題文

高橋君はRPGゲームをプレイしています。

このゲームには N 個の部屋が一列に並んだダンジョンがあります。部屋は入口側から奥に向かって 1, 2, \ldots, N と番号付けられており、各部屋にはモンスターが1体ずつ待ち構えています。部屋 i (1 \leq i \leq N) にいるモンスターの強さは V_i です。

高橋君は初期の強さが W のスライムを操作して、このダンジョンを攻略します。スライムは部屋 1 から部屋 N まで、1, 2, \ldots, N の順に各部屋をちょうど1回ずつ訪れます。途中で引き返したり、部屋を飛ばしたりすることはできません。

スライムがある部屋を訪れた時点での強さを「現在の強さ」と呼びます。スライムの現在の強さは、初期の強さ W に、その部屋を訪れるまでに吸収した全てのモンスターの強さの合計を加えた値です。

スライムが部屋 i を訪れたとき、以下の2つの場合のうちいずれか一方が起こります。

  • モンスターの強さ V_i がスライムの現在の強さ以下である場合（V_i がスライムの現在の強さと等しい場合を含む）、スライムはそのモンスターを吸収します。スライムの強さに V_i が即座に加算され、加算後の値が次の部屋以降での現在の強さとなります。
  • モンスターの強さ V_i がスライムの現在の強さより真に大きい場合、スライムはそのモンスターを吸収できず、スライムの強さは変化しません。

スライムが部屋 1 から部屋 N まで全ての部屋を順に訪れ終わった後の、スライムの強さを求めてください。

制約

  • 1 \leq N \leq 2 \times 10^5
  • 1 \leq W \leq 10^9
  • 1 \leq V_i \leq 10^9 (1 \leq i \leq N)
  • 入力はすべて整数
  • 答えは 2^{63} 未満に収まることが保証されます（符号付き 64 ビット整数に収まります）。ただし、符号付き 32 ビット整数の範囲（2^{31}-1 以下）を超える場合があります。

入力

N W
V_1 V_2 \cdots V_N
  • 1 行目には、部屋の数を表す整数 N と、スライムの初期の強さを表す整数 W が、スペース区切りで与えられる。
  • 2 行目には、各部屋にいるモンスターの強さを表す整数 V_1, V_2, \ldots, V_N が、スペース区切りで与えられる。

出力

ダンジョン攻略後のスライムの強さを整数で 1 行に出力せよ。

入力例 1

5 3
2 4 1 3 7

出力例 1

20

入力例 2

8 5
3 6 2 10 4 8 1 20

出力例 2

59

入力例 3

10 1
1 3 2 5 100 4 6 3 2 1000000000

出力例 3

19

Score : 233 pts

Problem Statement

Takahashi is playing an RPG game.

In this game, there is a dungeon consisting of N rooms arranged in a row. The rooms are numbered 1, 2, \ldots, N from the entrance toward the back, and each room has one monster waiting inside. The strength of the monster in room i (1 \leq i \leq N) is V_i.

Takahashi controls a slime with an initial strength of W to conquer this dungeon. The slime visits each room exactly once in order from room 1 to room N, visiting them in the order 1, 2, \ldots, N. It cannot turn back or skip rooms.

The "current strength" of the slime at the time it visits a room is defined as the initial strength W plus the total strength of all monsters absorbed before visiting that room.

When the slime visits room i, exactly one of the following two cases occurs:

  • If the monster's strength V_i is less than or equal to the slime's current strength (including the case where V_i equals the slime's current strength), the slime absorbs the monster. V_i is immediately added to the slime's strength, and the value after the addition becomes the current strength for subsequent rooms.
  • If the monster's strength V_i is strictly greater than the slime's current strength, the slime cannot absorb the monster, and the slime's strength does not change.

Find the slime's strength after it has visited all rooms from room 1 to room N in order.

Constraints

  • 1 \leq N \leq 2 \times 10^5
  • 1 \leq W \leq 10^9
  • 1 \leq V_i \leq 10^9 (1 \leq i \leq N)
  • All input values are integers.
  • It is guaranteed that the answer fits in less than 2^{63} (it fits in a signed 64-bit integer). However, it may exceed the range of a signed 32-bit integer (2^{31}-1 or less).

Input

N W
V_1 V_2 \cdots V_N
  • The first line contains an integer N representing the number of rooms and an integer W representing the slime's initial strength, separated by a space.
  • The second line contains integers V_1, V_2, \ldots, V_N representing the strength of the monster in each room, separated by spaces.

Output

Output the slime's strength after conquering the dungeon as an integer on a single line.

Sample Input 1

5 3
2 4 1 3 7

Sample Output 1

20

Sample Input 2

8 5
3 6 2 10 4 8 1 20

Sample Output 2

59

Sample Input 3

10 1
1 3 2 5 100 4 6 3 2 1000000000

Sample Output 3

19