Tangerine Tree

Time limit1sMemory limit1024 MB

Summary

Each day, N pickers take fixed amounts from a tree with M tangerines in order, and the task is to find how many remain after 10^100 days.

Level: Medium7 of 10
Topics: Simulation, Math, Implementation
Solved: No attempts yet

Problem

Seoyun's backyard has a large tangerine tree with $M$ tangerines on it.

$N$ Gomgomi from the house next door come to pick tangerines from this tree every day. Every day, they try in order, starting with Gomgomi 1 and ending with Gomgomi $N$ . Gomgomi $i$ tries to pick $A_i$ tangerines. If fewer than $A_i$ tangerines remain on the tree, Gomgomi $i$ does nothing.

Find the number of tangerines left on the tree after $10^{100}$ days.

Input

The first line contains the number of Gomgomi $N$ and the number of tangerines $M$ , separated by a space. ( $1 \leq N \leq 200\,000$ , $1 \leq M \leq 10^{18}$ )

The second line contains the amounts $A_1, A_2, \cdots, A_N$ that each Gomgomi tries to pick, separated by spaces. ( $1 \leq A_i \leq 10^{12}$ )

All numbers in the input are integers.

Output

Print the number of tangerines left on the tree after $10^{100}$ days.

Examples1

Example 1
Input
```
3 19
2 5 4
```
Expected output
```
1
```