Special Serving

Interview

Time limit1sMemory limit512 MB

Summary

Given N values x_i, find the fewest students to switch from pamuntwi to eggplant so the running sum never reaches M.

Level: Medium5 of 10
Topics: Greedy, Heap
Solved: No attempts yet

Problem

???: Eggplant? They don't even look alike...

NLCS Jeju likes to serve pamuntwi (fried beef breaded with Parmesan).

Students would rather eat fresh eggplant than pamuntwi!

$N$ students stand in a cafeteria line one after another. When the $i$ -th student from the front gets pamuntwi instead of eggplant, their dissatisfaction rises by $x_i$ . When they get eggplant, it drops by $x_i$ . The initial dissatisfaction is $0$ .

Food is served to students in order from the front. If the dissatisfaction ever reaches $M$ or more at any moment, the students stage an 'eggplant movement.'

Write a program that finds the minimum number of eggplants needed to prevent any eggplant movement.

Input

The first line contains $N$ and $M$ , separated by a space.

The second line contains $N$ integers $x_i$ , separated by spaces.

Output

On the first line, print the minimum number of eggplants needed to prevent the students from staging an eggplant movement.

Constraints

$1 \leq N \leq 200\,000$
$1 \leq M \leq 10^9$
$0 \leq x_i \leq 10^9$

Examples2

Example 1
Input
```
5 3
0 0 2 0 2
```
Expected output
```
1
```
Example 2
Input
```
10 90
14 6 12 16 14 6 20 19 16 12
```
Expected output
```
2
```