USACO 1.3 Mixing Milk 程序

{
ID:cxj6661
PROB:milk
LANG:PASCAL
}
//By Ceeji
//Date: 2009-6-1
//Type: Sort
//Resource: USACO 1.3
Program milk;
Const
   fin='milk.in';
   fou='milk.out';
Type nm=record
          p,a:longint;
        end;
Var
   i,n,m,sum:longint;
   info:array[1..5000]of nm;
Procedure qsort(s,t:longint);
var tmp:nm;
    e,i,j:longint;
begin
    i:=s; j:=t; e:=info[random(t-s+1)+s].p;
    repeat
       while (i<t)and(info[i].p<e) do inc(i);
       while (j>s)and(info[j].p>e) do dec(j);
       if i<=j then
       begin
          tmp:=info[i]; info[i]:=info[j]; info[j]:=tmp;
          inc(i); dec(j);
       end;
    until i>j;
    if j>s then qsort(s,j);
    if i<t then qsort(i,t);
end;
begin
   randomize;
   assign(input,fin);  reset(input);
   assign(output,fou); rewrite(output);
   readln(n,m);
   for i:=1 to m do
   begin
     readln(info[i].p,info[i].a);
   end;
   close(input);
   sum:=0;
   qsort(1,m); i:=1;
   while n>0 do
   begin
      if n>info[i].a then
      begin
         inc(sum,info[i].p*info[i].a);
         dec(n,info[i].a);
         inc(i);
      end
      else
      begin
         inc(sum,info[i].p*n); n:=0; break;
      end;
   end;
   writeln(sum);
   close(output);
end.