http://acm.pku.edu.cn/JudgeOnline/problem?id=1180

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

Имеется последовательность N заданий, предназначенных для выполнения на одной машине. Задания пронумерованы от 1 до N следующим образом 1, 2, …, 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 заданий.

ВВОД

Ваша программа должна читать данные со стандартного ввода. Первая строка содержит количество заданий N (1 <= N <= 10000). Вторая строка содержит подготовительное время S, которое является целым числом (0 <= S <= 50). Следующие N строк содержат информацию о заданиях 1, 2, …, N в указанном порядке. В каждой из этих строк первым задается целое число Ti (1 <= Ti <= 100) - время выполнения задания. За ним следует целое число Fi (1 <= Fi <= 100) - стоимостный коэффициент задания.

ВЫВОД

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

ПРИМЕР ВХОДНЫХ И ВЫХОДНЫХ ДАННЫХ

Пример 1:   
ввод             вывод
2    45000
50
100 100
100 100

Пример 2:     
ввод                                        вывод
5                     153
1
1 3
3 2
4 3
2 3
1 4

Пример 2 соответствует примеру из текста задачи.

ПРИМЕЧАНИЕ

Для каждого теста общая стоимость любой группировки не превосходит 2^31 - 1.

Program Gp ;

Const
    maxn = 10001 ;

Var
    sumT , sumC                         : array[ 0 .. maxn ] of longint ;
    f                                   : array[ 0 .. maxn ] of longint ;
    que                                 : array[ 0 .. maxn ] of longint ;
    n , m                               : longint ;

Procedure Init ;
var
    i , a , b                           : longint ;
begin
    readln( n ) ; readln( m ) ;
    for i := 1 to n do readln( sumT[ i ] , sumC[ i ] ) ;
    sumT[ n + 1 ] := 0 ; sumC[ n + 1 ] := 0 ;
    for i := n downto 1 do sumT[ i ] := sumT[ i + 1 ] + sumT[ i ] ;
    for i := n downto 1 do sumC[ i ] := sumC[ i + 1 ] + sumC[ i ] ;
end ;

Function Sploe( j1 , j2 : longint ) : extended ;
begin
    Sploe := ( f[ j1 ] - f[ j2 ] ) / ( sumT[ j1 ] - sumT[ j2 ] ) ;
end ;

Procedure Dp ;
var
    l , r , i                           : longint ;
begin
    f[ n + 1 ] := 0 ;
    l := 1 ; r := 1 ; que[ 1 ] := n + 1 ;
    for i := n downto 1 do
    begin
        while ( r > l ) and ( Sploe( que[ l ] , que[ l + 1 ] ) <= sumC[ i ] ) do Inc( l ) ;
        f[ i ] := f[ que[ l ] ] + ( m + sumT[ i ] - sumT[ que[ l ] ] ) * sumC[ i ] ;
        while ( r > l ) and ( Sploe( que[ r - 1 ] , que[ r ] ) >= Sploe( que[ r ] , i ) ) do Dec( r ) ;
        Inc( r ) ; que[ r ] := i ;
    end ;
    writeln( f[ 1 ] ) ;
end ;

Begin
    Init ;
    Dp ;
end .