Caisa уже купил сахар и теперь идет домой. Во время пути домой он решил пройти игру на своем мобильном телефоне.

В игре есть (n + 1) колонн, пронумерованных от 0 до n. Нулевая колонна имеет высоту 0, i-я (i > 0) колонна имеет высоту h_i. Цель игры — добраться до n-й колонны, при этом единственное действие, которое может совершать игрок: перепрыгнуть с текущей колонны (обозначим ее номер переменной k) на следующую колонну (ее номер равен k + 1). После описанного прыжка энергия игрока увеличивается на h_k - h_k + 1 (если это значение меньше нуля, то игрок теряет соответствующее количество энергии). По правилам игры в любой момент времени энергия игрока должна быть неотрицательной.

Изначально Caisa стоит на нулевой колонне и имеет ноль единиц энергии. Также в игре есть специально оплачиваемая возможность: за один доллар игрок может увеличить высоту любой колонны на единицу. Caisa может использовать эту возможность несколько раз, но, конечно, он не хочет тратить слишком много денег. Какое минимальное количество денег ему придется потратить, чтобы пройти игру?