onst
    ProgramName='software';
Var
    i,j,k,n,m,l,r,s,t,x,y:longint;
    a:array[0..110,1..2]of longint;
    f:array[0..110,0..110]of longint;
    ans,mid:longint;
 
Procedure Pin;
var
    i,j,k:longint;
begin
    readln(n,m);
    for i:=1 to n do
        readln(a[i,1],a[i,2]);
end;
 
 
Function max(x,y:longint):longint;
begin
    if x>y then exit(x) else exit(y);
end;
 
 
Function get(day:longint):longint;
var
    i,j,k:longint;
begin
    for i:=0 to n do
        for j:=0 to m do
            f[i,j]:=-1000000;
    f[0,0]:=0;
    get:=0;
    for i:=1 to n do
        for j:=0 to m do
            for k:=0 to j do
                if day-a[i,1]*k>=0 then
                    f[i,j]:=max(f[i,j],f[i-1,j-k]+(day-a[i,1]*k) div a[i,2]);
    exit(f[n,m]);
end;
 
 
Procedure Main;
var
    i,j,k:longint;
begin
    r:=1;
    repeat
        r:=r*2;
    until get(r)>m;
    l:=r-r div 2;
    repeat
        mid:=(l+r)shr 1;
        t:=get(mid);
        if t>=m then
            begin
                ans:=mid;
                r:=mid-1;
            end
        else
            l:=mid+1;
    until l>r;
end;
 
 
Procedure Pout;
var
    i,j,k:longint;
begin
    writeln(ans);
end;
 
 
begin
    assign(input,ProgramName+'.in');
    assign(output,ProgramName+'.out');
    reset(input);
    rewrite(output);
    pin;
    main;
    pout;
    close(input);
    close(output);
end.