记录编号	13676	评测结果	AAAAAAAAAA
题目名称	[IOI 2002] 任务安排	最终得分	100
用户昵称	Achilles	是否通过	通过
代码语言	Pascal	运行时间	0.031 s
提交时间	2009-10-07 21:53:40	内存使用	0.19 MiB

program batch ;

const
    maxn=5001;
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
	    l:=l+1;
        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
	    r:=r-1;
        r:=r+1;
        que[r]:=i;
    end ;
    writeln(f[1]);
end ;
Begin
    assign(input,'batch.in');
    assign(output,'batch.out');
    reset(input);
    rewrite(output);
    init;
    dp;
    close(input);
    close(output);
end .