\begin{problem}{Cheezy dibbles}{dibbles.in}{dibbles.out}{2 секунды}{256 мегабайт}

%Автор задачи: Евгений Замятин
%Автор условия: Евгений Замятин

В кои-то веки Шкипер решил отдохнуть и насладиться пачкой его любимых чипсов <<Cheezy dibbles>>. Однако Шкипер и не подозревал, что в таком, казалось бы,
простом деле, его могут поджидать трудности. 

Суть проблемы такова:
перед Шкипером в ряд выложены $n$ пачек его любимого лакомства. Пачки нумеруются с единицы, начиная с самой левой. 
В $i$-й из них лежит $a_i$ чипсов. Каждую секунду Шкипер может
выбрать отрезок с началом в пачке с номером $l$ и концом в пачке с номером $r$ и съесть по чипсе из каждой пачки этого отрезка. 
Но он не желает тратить энергию впустую, а именно, он может выбирать отрезок только если в каждой пачке из этого отрезка есть хотя бы одна чипса.

Помогите Шкиперу посчитать максимальное количество пачек, которые он сможет опустошить за $k$ секунд! 
Пачка чипсов считается пустой, если количество чипсов в ней равно нулю.

\InputFile
В первой строке входного файла дано два числа $n, k$ ($1 \le n \le 2000, 1 \le k \le 10^9$)~--- количество пачек чипсов и время в секундах, 
которое есть у Шкипера на еду.

Во второй строке даны $n$ чисел $a_i$ ($1 \le a_i \le 10^9$)~--- количество чипсов в $i$-й пачке.

\OutputFile
В единственной строке выходного файла выведите максимальное количество пустых пачек, которое может получиться через $k$ секунд, если Шкипер действует
согласно своему алгоритму.
      
\Example
\begin{example}%
\exmp{
6 5
1 5 3 2 1 4        
}{
5
}%
\end{example}

\Testing
Первая группа тестов состоит из тестов, для которых выполняется ограничение $n \le 10, k \le 5$. Баллы 
за эту группу начисляются только при прохождении всех тестов группы. Стоимость группы составляет $20$ баллов.  

Вторая группа тестов состоит из тестов, для которых выполняется ограничение $n \le 100, k \le 100$. Баллы       
за эту группу начисляются только при прохождении всех тестов группы. Стоимость группы составляет $30$ баллов.

Третья группа тестов состоит из тестов, для которых выполняется ограничение $n \le 100, k \le 10^9$. Баллы       
за эту группу начисляются только при прохождении всех тестов группы. Стоимость группы составляет $30$ баллов.

Четвертая группа тестов состоит из тестов, для которых выполняется ограничение $n \le 2000, k \le 10^9$. Баллы       
за эту группу начисляются только при прохождении всех тестов группы. Стоимость группы составляет $20$ баллов.

Обратите внимание на возможность узнать результат проверки вашего решения на всех группах тестов, 
нажав на ссылку <<\texttt{Request feedback}>> на вкладке <<\texttt{Runs}>>.

\end{problem}


