Правительство Марса заинтересовано не только в оптимизации космических перелетов, но и в улучшении дорожной системы планеты.

Одна из самых важных магистралей Марса соединяет Олимп-Сити и Кцолоп, столицу Кидонии. В рамках этой задачи будем рассматривать только путь от Кцолопа до Олимп-Сити, но не обратный путь (от Олимп-Сити до Кцолопа).

Дорога от Кцолопа до Олимп-Сити имеет длину $$$\ell$$$ километров. Каждая точка дороги имеет координату $$$x$$$ ($$$0 \le x \le \ell$$$) — расстояние до Кцолопа в километрах. Таким образом, Кцолоп находится в точке с координатой $$$0$$$, а Олимп-Сити — в точке с координатой $$$\ell$$$.

На дороге стоит $$$n$$$ дорожных знаков, на $$$i$$$-м из которых написано ограничение скорости $$$a_i$$$. Это ограничение означает, что следующий километр следует проехать за $$$a_i$$$ минут и действует до тех пор, пока по пути не встретится следующий дорожный знак. Один из дорожных знаков стоит в самом начале дороги (т. е. в точке с координатой $$$0$$$) и задает начальную скорость.

Зная расположение всех дорожных знаков, нетрудно вычислить время поездки от Кцолопа до Олимп-Сити. Рассмотрим пример:

В данном случае необходимо проехать первые три километра за пять минут каждый, затем — один километр за восемь минут, затем — еще четыре километра за три минуты каждый и, наконец, последние два километра за шесть минут каждый. Итого время в пути составит $$$3\cdot 5 + 1\cdot 8 + 4\cdot 3 + 2\cdot 6 = 47$$$ минут.

С целью оптимизации движения правительство Марса решило убрать не более $$$k$$$ дорожных знаков. При этом знак в начале дороги убирать нельзя, иначе на начальном отрезке пути не будет никаких ограничений. Убирать знаки необходимо таким образом, чтобы минимизировать время в пути от Кцолопа до Олимп-Сити.

В Кидонии сосредоточены крупные промышленные предприятия Марса, поэтому оптимизация дороги до Олимп-Сити является приоритетной задачей. По этой причине правительство Марса поручило Вам решить эту задачу и выяснить, какие знаки необходимо убрать.