Hide

Problem K
Beach

Maja has had enough of all the big seaside estates that occupy the coastline. Instead, she wants to create a long and beautiful beach that anyone can use. She is planning to buy a segment of plots along the coast to create the beach.

Maja has a budget of $B$ kronor, and the plots along the coast cost $A_{0}, A_{1}, \dots, A_{N - 1}$ kronor, from left to right. Maja can buy one segment of adjacent plots. What is the longest segment of plots that she can afford to buy?

Input

The first line contains the two integers $N$ and $B$ , the number of plots and Maja’s budget.

The second line contains $N$ integers $A_{0}, A_{1}, \dots, A_{N - 1}$ , the costs of the plots.

Output

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

Constraints and Scoring

$1 \leq N \leq 10^{5}$ .
$0 \leq B \leq 10^{9}$ .
$1 \leq A_{i} \leq 1000$ for each $i$ such that $0 \leq i \leq N - 1$ .

Your solution will be tested on a set of test groups, each worth a number of points. Each test group contains a set of test cases. To get the points for a test group you need to solve all test cases in the test group.

Group	Score	Limits
$1$	$21$	$A_{0} = A_{1} = \dots = A_{N - 1}$
$2$	$30$	$N \leq 500$
$3$	$49$	No additional constraints

Example

In the first example, Maja has enough money to buy all the plots.

In the second example, Maja can buy either the first three, or the last three plots.

In the third example, Maja can buy the plots with indices $2, 3, 4, 5, 6$ and $7$ . This will cost $3 + 4 + 6 + 2 + 1 + 2 = 18$ kronor, which Maja can afford. However, it is not possible to buy more than $6$ plots.

Sample Input 1	Sample Output 1
3 14 4 7 3	3

Sample Input 2	Sample Output 2
4 36 11 5 7 14	3

Sample Input 3	Sample Output 3
9 18 1 5 3 4 6 2 1 2 4	6

Attachments

statement_az-AZ.pdf statement_bg-BG.pdf statement_cs-CZ.pdf statement_de-CH.pdf statement_de-DE.pdf statement_de-TC.pdf statement_el-GR.pdf statement_es-ES.pdf statement_es-MX.pdf statement_et-EE.pdf statement_fi-FI.pdf statement_fr-FR.pdf statement_he-IL.pdf statement_hr-HR.pdf statement_hu-HU.pdf statement_hy-AM.pdf statement_is-IS.pdf statement_it-IT.pdf statement_ja-JP.pdf statement_kk-KZ.pdf statement_lt-LT.pdf statement_mn-MN.pdf statement_nb-NO.pdf statement_nl-NL.pdf statement_pt-BR.pdf statement_ro-MD.pdf statement_ro-RO.pdf statement_ru-KG.pdf statement_sk-SK.pdf statement_sl-SI.pdf statement_sv-SE.pdf statement_sv-TS.pdf statement_uk-UA.pdf statement_zh-US.pdf

Problem KBeach

Input

Output

Constraints and Scoring

Example

Problem K
Beach