先把面值从大到小排序
然后从头往尾扫，只要不超额，能取多少去多少
然后如果还有剩余，就从尾往头扫，尽量取，让他恰好超额
这样差不多就对了，但还要优化，否则tle
记录每一次各面额取了多少，看看这样取还可以取多少次，就免去了重复计算

7691948 xuhaoran510 3040 Accepted 892K 0MS Pascal 1298B 2010-10-02 13:47:15 

type
atype=record
        wg,count:longint;
      end;

var
N,C,i,j,now,x,ans,min:longint;
a:array[0..30] of atype;
b:array[0..30] of longint;
temp:atype;

begin
readln(N,C);
for i:=1 to n do readln(a[i].wg,a[i].count);

for i:=1 to n-1 do
  for j:=i+1 to n do
    if a[i].wg<a[j].wg then
    begin temp:=a[i];
          a[i]:=a[j];
          a[j]:=temp;
    end;

repeat
  now:=C;
  fillchar(b,sizeof(b),0);
  for i:=1 to n do
    if a[i].count<>0 then
    begin x:=now div a[i].wg;
          if a[i].count<x then x:=a[i].count;
          dec(a[i].count,x);
          now:=now-x*a[i].wg;
          b[i]:=x;
          if now=0 then break;
    end;

  if now>0 then
  begin for i:=n downto 1 do
        begin x:=now div a[i].wg;
              if x*a[i].wg<>now then inc(x);
              if a[i].count<x then x:=a[i].count;
              dec(a[i].count,x);
              inc(b[i],x);
              now:=now-x*a[i].wg;
              if now<=0 then break;
        end;
        if now>0 then break;
  end;

  min:=maxlongint;
  for i:=1 to n do
    if b[i]<>0 then
      if a[i].count div b[i]<min then
        min:=a[i].count div b[i];

  for i:=1 to n do
    dec(a[i].count,b[i]*min);

  inc(ans,min+1);

until false;
writeln(ans);
end.