Badstrand

Interview

Time limit1sMemory limit1024 MB

Summary

Given plot prices along a coast and a budget B, find the longest contiguous run of plots whose total price is at most B.

Level: Easy3 of 10
Topics: Sliding window, Array, Two pointers
Solved: No attempts yet

Problem

Maja is tired of the coast being taken up by large lakeside plots. She wants to build a long, nice beach that the public can use. She plans to buy a contiguous segment of plots along the coast to create the beach.

Maja has a budget of $B$ kronor. The plots along the coast cost $A_1, A_2, \dots, A_N$ kronor from left to right. What is the longest segment of plots that Maja can afford to buy?

Input

The first line contains two integers $1 \leq N \leq 10^5$ and $0 \leq B \leq 10^9$ , the number of plots and Maja's budget.

The second line contains $N$ positive integers $A_1, A_2, \dots, A_N$ ( $1 \le A_i \le 1\,000$ ), where the $i$ -th number is the price of plot $i$ .

Output

Print one integer, the largest number of adjacent plots that Maja can afford to buy.

Limits

$N \leq 10^5$

Examples3

Example 1
Input
```
3 14
4 7 3
```
Expected output
```
3
```
Example 2
Input
```
4 36
11 5 7 14
```
Expected output
```
3
```
Example 3
Input
```
9 18
1 5 3 4 6 2 1 2 4
```
Expected output
```
6
```