Cow Dance Show#10547
After several months of rehearsal, the cows are just about ready to put on their annual dance performance. This year, they are performing the famous bovine ballet "Cowpelia."
The only aspect of the show that remains to be determined is the size of the stage. A stage of size can support cows dancing simultaneously. The cows in the herd are numbered 1, \ldots, n in the order in which they must appear in the dance. Each cow plans to dance for a specific duration of time .
Initially, cows 1, \ldots, k appear on stage and start dancing. When the first of these cows finishes her part, she leaves the stage, and cow k + 1 immediately starts dancing. This process continues, so there are always cows dancing simultaneously (until the end of the show, when there are fewer than cows remaining).
The show ends when the last cow finishes her dancing part, at time .
Clearly, the larger the value of , the smaller the value of . Since the show cannot last too long, you are given an upper bound T_{\max} on the duration of the performance. Subject to this constraint, determine the smallest possible value of .
The first line contains n~(1 \le n \le 10000) and T_{\max}, where T_{\max} is an integer not exceeding 10^6.
The next lines contain the durations d(1), \ldots, d(n) of the dancing parts for cows 1, \ldots, n, respectively. Each is an integer in the range 1, \ldots, 10^5.
It is guaranteed that when k=n, the show finishes within the time limit.
Print the smallest possible value of such that the dance performance takes no more than T_{\max} units of time.
Example 1