Задача . D. Жара

Между официальной столицей Берляндии и ее культурной столицей есть единственная дорога, пролегающая через n областей. В каждой области свой уникальный климат, поэтому летом в i-ой (1 ≤ i ≤ n) области стоит устойчивая температура t_i градусов.

Этим летом группа из m школьников хочет добраться из официальной столицы в культурную для посещения музеев и достопримечательностей. Для перевоза школьников между городами организаторы экскурсии используют автобусы, но в них иногда бывает очень жарко, точнее, если при проезде i-ой области в некотором автобусе находятся k школьников, то температура внутри автобуса равна t_i + k градусов.

Разумеется, мало кому нравится, когда в автобусе жарко, и поэтому, если при проезде i-ой области температура в некотором автобусе больше, чем T_i градусов, то каждый из школьников в этом автобусе требует неустойку за некомфортные условия в размере x_i рублей, причем, неустойка взымается в каждой области, где температура в автобусе превышает установленный предел.

Для экономии денег организаторы поездки могут в начале поездки и между областями произвольным образом менять количество автобусов (конечно же, для проезда любой области требуется хотя бы один автобус), на которых едут дети, а также произвольным образом пересаживать их между автобусами, однако, каждый из автобусов на i-ом участке обойдется организаторам в cost_i рублей. Обратите внимание, что плата за пересадку не взимается.

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