Задания в пакете
Первоисточник: Неофициальный сайт белорусских олимпиад. Задачи со сборов к IOI (2002-2003). Пакетная обработка заданий
URL первоисточника: http://byoi.narod.ru/
Задачу добавил: elena
Успешно сдано решений: 0
Существует последовательность N заданий, предназначенных для выполнения на одном компьютере. Все задания последовательно пронумерованы от 1 до N. Нужно сгруппировать задания в один или несколько пакетов так, чтобы каждый пакет состоял из следующих друг за другом заданий исходной последовательности. Выполнение первого задания начинается в момент времени 0.
Пакеты обрабатываются один за другим, начиная с первого, следующим образом. Если пакет b содержит задания с меньшими номерами, чем пакет c, то пакет b поступает на обработку раньше пакета c. Задания каждого пакета выполняются на компьютере последовательно. Сразу же после того, как все задания пакета выполнены, компьютер выводит результаты выполнения всех заданий этого пакета. Время завершения выполнения j-го задания определяется временем завершения обработки всего пакета, содержащего j-ое задание.
Чтобы подготовить компьютер к обработке каждого пакета, необходимо время S, которое назовем подготовительным. Для каждого i-го задания известен стоимостный коэффициент Fi и время Ti, необходимое для выполнения этого задания. Если пакет состоит из заданий x, x+1, … , x+k и поступает на обработку в момент времени t, то время завершения выполнения каждого задания пакета рассчитывается по формуле t + S + (Tx + Tx+1 + … + Tx+k). Заметим, что машина выводит результаты всех заданий пакета в один и тот же момент времени.
Если время завершения выполнения i-го задания - Oi, то стоимость выполнения этого задания составит Oi x Fi.
Пусть имеется 5 заданий и известно: S = 1; (T1, T2, T3, T4, T5) = (1, 3, 4, 2, 1); (F1, F2, F3, F4, F5) = (3, 2, 3, 3, 4).
Если задания сгруппированы в три пакета {1, 2}, {3}, {4, 5}, то можно вычислить время завершения выполнения для них (O1, O2, O3, O4, O5) = (5, 5, 10, 14, 14) и стоимости выполнения заданий (15, 10, 30, 42, 56), соответственно. Общая стоимость выполнения сгруппированных в пакеты заданий определяется как сумма стоимостей выполнения каждого задания. Таким образом, общая стоимость выполнения всех заданий для предложенного примера будет равна 153.
Задана величина подготовительного времени S и последовательность N заданий, для каждого из которых определено время выполнения и стоимостный коэффициент. Требуется написать программу, которая вычисляет минимально возможную общую стоимость выполнения последовательности N заданий.
Формат входного файла input.txt:
Первая строка содержит целое число N - количество заданий N (1 <= N <= 10000).
Вторая строка содержит целое число S - подготовительное время (0 <= S <= 50).
Следующие N строк содержат информацию о заданиях 1, 2, …, N в указанном порядке. В каждой из этих строк первым задается целое число Ti (1 <= Ti <= 100) - время выполнения задания. За ним следует целое число Fi (1 <= Fi <= 100) - стоимостный коэффициент задания.
Формат выходного файла output.txt:
Первая строка - одно целое число - минимальная общая стоимость выполнения последовательности N заданий.
Примечание.
Для каждого теста общая стоимость любой группировки не превосходит 2^31 - 1.
Пример входного файла #1
2
50
100 100
100 100
Пример выходного файла #1
45000
Пример входного файла #2
5 1
1 3
3 2
4 3
2 3
1 4
Пример выходного файла #2
153
(соответствует примеру из текста задачи).