Cheezy dibbles

이번에는 스키퍼가 쉬면서 좋아하는 과자 한 봉지인 『Cheezy dibbles』를 즐기기로 했다. 그러나 이처럼 단순해 보이는 일에도 어려움이 생길 수 있다는 것을 스키퍼는 전혀 몰랐다.

문제는 다음과 같다. 스키퍼 앞에 좋아하는 과자 봉지 $n$개가 일렬로 놓여 있다. 봉지는 가장 왼쪽부터 1번으로 번호가 매겨진다. $i$번째 봉지에는 과자가 $a_i$개 들어 있다. 스키퍼는 1초마다 봉지 $l$에서 시작해 봉지 $r$에서 끝나는 구간을 고르고, 그 구간에 있는 각 봉지에서 과자를 하나씩 먹을 수 있다. 다만 에너지를 낭비하고 싶지 않아서, 구간 안의 모든 봉지에 과자가 적어도 하나씩 남아 있을 때만 구간을 고른다. 스키퍼가 $k$초 안에 비울 수 있는 봉지의 최대 개수를 구하라. 과자가 0개인 봉지를 빈 봉지로 본다.

첫째 줄에 두 정수 $n$, $k$가 주어진다 ($1 \le n \le 2000$, $1 \le k \le 10^9$). $n$은 과자 봉지의 개수이고, $k$는 스키퍼가 과자를 먹는 데 쓸 수 있는 시간(초)이다. 둘째 줄에는 $n$개의 정수 $a_1, a_2, \ldots, a_n$이 주어진다 ($1 \le a_i \le 10^9$). $a_i$는 $i$번째 봉지에 들어 있는 과자의 개수이다.

스키퍼가 알고리즘에 따라 행동할 때, $k$초 후에 비어 있을 수 있는 봉지의 최대 개수를 한 줄에 출력한다.