29148번 - Cheezy dibbles 다국어

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

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

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

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

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

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