This page is still under construction.

Parts of this page are still being built. What you see may change.

Server

Interview

Time limit1sMemory limit256 MB

Summary
Count how many jobs from the front finish in request order before their total duration exceeds T.
Level

Easy1 of 10

Topics
Prefix sum, Simulation
Solved
No attempts yet

Problem

You run a server that handles requested jobs under the FCFS (First-Come, First-Served) rule. Each day you can give the server at most TT minutes of time. You want to know how many jobs finish within today's time.

FCFS handles jobs only in the order the requests arrived. You cannot skip a job to handle a later one first, and once the remaining time is too short to finish a job, none of the jobs after it are handled either.

Suppose T=180T = 180 and the job durations, in request order, are 45, 30, 55, 20, 80, and 20 minutes. Then 4 jobs finish. The first four jobs take 150 minutes in total and fit inside the given time, but the first five take 230 minutes, which is more than 180. The sixth job on its own would fit in the remaining time, but the fifth job never finished, so the sixth job is not handled.

Input

The first line contains two integers nn and TT (1≤n≤501 \le n \le 50, 1≤T≤5001 \le T \le 500), where nn is the number of jobs.

The second line contains nn natural numbers in request order. Each number is at most 100 and gives that job's duration in minutes.

Output

Print how many jobs finish within TT minutes when the jobs are handled under the FCFS rule.

Examples2

  1. Example 1

    Input
    6 180
    45 30 55 20 80 20
    
    Expected output
    4
    
  2. Example 2

    Input
    10 60
    20 7 10 8 10 27 2 3 10 5
    
    Expected output
    5