Задача Пакетная обработка заданий

Описание

Имеется последовательность N заданий, предназначенных для выполнения на одной машине. Задания пронумерованы от 1 до N следующим образом 1, 2, . . . N . Задания должны быть так сгруппированы в один или несколько пакетов, чтобы каждый пакет состоял из следующих друг за другом заданий исходной последовательности. Выполнение первого задания начинается в момент времени 0. Пакеты обрабатываются один за другим, начиная с первого, следующим образом. Если пакет b содержит задания с меньшими номерами, чем пакет c , то пакет b поступает на обработку раньше пакета c . Задания каждого пакета выполняются на машине последовательно. Сразу же после того, как все задания пакета выполнены, машина выводит результаты выполнения всех заданий этого пакета. Время завершения выполнения j-го задания определяется временем завершения обработки всего пакета, содержащего j-ое задание.

Чтобы подготовить машину к обработке каждого пакета, необходимо время S , которое назовем подготовительным. Для каждого i-го задания известен стоимостный коэффициент F _i и время T _i , необходимое для выполнения этого задания. Если пакет состоит из заданий x, x+1, . . . , x+k и поступает на обработку в момент времени t , то время завершения выполнения каждого задания пакета рассчитывается по формуле t + S + (T _x + T _x+1 + . . . + T _x+k ) . Заметим, что машина выводит результаты всех заданий пакета в один и тот же момент времени. Если время завершения выполнения i-го задания --- O _i , то стоимость выполнения этого задания составит O _i x F _i .

Пусть имеется 5 заданий и известно:
S=1
(T ₁ , T ₂ , T ₃ , T ₄ , T ₅ ) = (1, 3, 4, 2, 1)
(F ₁ , F ₂ , F ₃ , F ₄ , F ₅ ) = (3, 2, 3, 3, 4)
Если задания сгруппированы в три пакета {1, 2} , {3} , {4, 5} , то можно вычислить время завершения выполнения для них (O ₁ , O ₂ , O ₃ , O ₄ , O ₅ ) = (5, 5, 10, 14, 14) и стоимости выполнения заданий (15, 10, 30, 42, 56) , соответственно. Общая стоимость выполнения сгруппированных в пакеты заданий определяется как сумма стоимостей выполнения каждого задания. Таким образом, общая стоимость выполнения всех заданий для предложенного примера будет равна 153.

Вам задана величина подготовительного времени S и последовательность N заданий, для каждого из которых определено время выполнения и стоимостный коэффициент. Требуется написать программу, которая вычисляет минимально возможную общую стоимость выполнения последовательности N заданий.

Формат входных данных

Первая строка содержит количество заданий N (1 ≤ N ≤ 10000) . Вторая строка содержит подготовительное время S, которое является целым числом (0 ≤ S ≤ 50) . Следующие N строк содержат информацию о заданиях 1, 2, . . . , N в указанном порядке. В каждой из этих строк первым задается целое число T _i (1 ≤ T _i ≤ 100) - время выполнения задания. За ним следует целое число F _i (1 ≤ F _i ≤ 100) - стоимостный коэффициент задания. Для каждого теста общая стоимость любой группировки не превосходит 2 ³¹ - 1 .

Формат выходных данных

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