Задача . C. Оптимизация дорог

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

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

Дорога от Кцолопа до Олимп-Сити имеет длину \(\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\) дорожных знаков. При этом знак в начале дороги убирать нельзя, иначе на начальном отрезке пути не будет никаких ограничений. Убирать знаки необходимо таким образом, чтобы минимизировать время в пути от Кцолопа до Олимп-Сити.

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