The Ice Cream Man's Children

The neighborhood ice cream man sets up his stall on the beach every day. However, not all days are good for him this summer when tourism is significantly reduced: some days he sells a lot of ice cream and makes a profit, while other days he sells few ice creams and incurs losses. For each day of the summer, we know whether he made a profit or a loss.

Our ice cream man has ~K~ children. We will consider a period of time "good" for him if the total profit he makes during this period allows him to give €1 to each of his children every day. For example, if ~K = 3~ and over a period of ~4~ days he has made a total of €15, then this period is good. Conversely, if over a period of ~6~ days he has made a total of €17, then this period is not good.

Help the ice cream man find the longest good period this summer.

Input:

The first line of input will contain two natural numbers, ~N~ and ~K~: the number of days in summer and the number of the ice cream man's children. The second line will contain ~N~ integers, separated in pairs by a space. Each integer corresponds to a day of the summer, in order. The integer will be positive if the ice cream man made a profit that day, negative if there was a loss, and zero if there was neither profit nor loss.

Output:

The output must contain one line with exactly one integer: the length of the longest good period.

Constraints:

• ~1 \le N \le 500.000~.
• 1 \le K \le 1.000~.
• Profit or loss each day will not exceed ~1.000.000.000~ in absolute value.
• The algebraic sum of profits or losses over any interval will not exceed ~1.000.000.000~ in absolute value.
• Time Limit: ~1~ sec.
• Memory Limit: ~64~ MB
• For test cases with a total value of ~60%~, it will be ~N \le 30.000~.
• For test cases with a total value of ~20%~, it will be ~N > 10.000~ and ~K = 1~.

Example of Input - Output:

input:

10 3
10 -8 -1 -11 6 12 -16 15 11 -13

output:

5

Explanation of the example:

The interval ~6~, ~12~, ~-16~, ~15~, ~11~ is good because it has a total profit of 28€ and lasts for ~5~ days. Therefore, the ice cream man can give ~5 \times 3 = 15~ € to his children and still have some left over. There is not a good period of longer duration.