Очень скоро на ТВ выйдет новое шоу с участием собак и их хозяев — Дог-Шоу. На шоу от собак требуется продемонстрировать бездонный желудок, стратегическое мышление и инстинкт самосохранения. Вы и ваша собака приглашены на шоу, и, конечно же, вы хотите выиграть!

Чтобы победить на шоу, собака должна съесть как можно больше мисок с едой (в чём поможет бездонный желудок). Собаки соревнуются отдельно друг от друга по следующим правилам:

В начале шоу на прямой находится собака в точке x = 0, а в точках x = 1, x = 2, ..., x = n находятся n мисок с едой. Миски пронумерованы от 1 до n слева направо. Как только начинается шоу, собака начинает бежать направо к ближайшей миске.

Еда в мисках в начале шоу слишком горячая и собака не может её съесть, пока она не остынет (инстинкт самосохранения мешает этому). Про i-ю из мисок известно, что еда в ней остынет через t_i секунд после начала шоу, и в этот момент собака сможет её съесть.

Собака съедает миску еды мгновенно. Собака перемещается от точки x до точки x + 1 за одну секунду. При этом собаке запрещено двигаться влево, она перемещается исключительно вправо и всегда со скоростью 1 единица расстояния в секунду. Когда собака достигает миски с едой, возможны следующие варианты:

• еда уже остыла, тогда собака мгновенно съедает еду и без какой-либо остановки продолжает двигаться вправо;
• еда ещё не остыла, тогда собака либо останавливается и ожидает, пока еда остынет, затем съедает её и тут же начинает двигаться вправо, либо без какой-либо остановки продолжает двигаться вправо, пропустив миску с едой.

Шоу останавливается через T секунд после начала. Если собака достигает миски с едой в момент ровно T, то она уже не успевает её съесть. Если до истечения T секунд собака убежала за самую правую из мисок, шоу останавливают досрочно.

Вы должны помочь вашей собаке составить стратегию, которая позволит ей съесть максимальное количество мисок с едой за T секунд.