View as PDF

Submit solution

Points: 7
Time limit: 2.0s
Memory limit: 256M

Problem type

Santa is on his merry way delivering presents and eating the cookies the kids have left out for him. Ho Ho Ho! He says, as he approaches the city of Toronto. Suddenly, Santa looks at his watch and realizes its almost morning! Luckily, he's almost done his trip, but he's saved the longest road for last.

Yonge Street is the longest street in the world, with N houses on it, numbered from 1 to N. House i is home to c_i children, each of whom is being delivered 1 present. You, after helping Santa ensure all the presents made it onto his sleigh, are now riding shotgun alongside Santa. Well, more like you're the driver, as Santa is too busy eating his cookies.

Dasher the reindeer tells Rudolph to touch down outside house 1, and you and Santa try to figure out how to best deliver the presents. As the much more experience one, Santa tells you to pick a single range of houses and deliver all presents to each house in the range; Santa can handle the rest.

You want to show Santa you were worthy of being brought along, but you also know you can only carry up to M presents. What is the greatest number of houses you can deliver presents to?


1 \le N, M \le 10^6

1 \le c_i \le 5

Input Specification

The first line of input contains two integers, N and M.

The second line of input contains N integers, the numbers of children in each house.

Output Specification

Output the greatest number of houses you can deliver presents to.

Sample Input

7 7
5 3 1 1 2 3 4

Sample Output


Sample Explanation

The ranges (2, 5) and (3, 6) are both of length 4 and are the longest possible ranges you could deliver presents to.


There are no comments at the moment.