Program CaM(input,output);
Var
    f:array[0..110,0..110] of longint;
    i,j,l,r,maxx:longint;
    n,m,mid,ans,c:longint;
    a,b:array[0..110] of longint;

Function max(x,y:longint):longint;
Begin
    if x>y then exit(x) else exit(y);
End;

Function check(x:longint):longint;
Var
    i,j,k:longint;
Begin
    for i:=0 to n do
        for j:=0 to m do
            f[i,j]:=-maxlongint div 2;
    f[0,0]:=0;
    for i:=1 to n do
        for j:=0 to m do
            for k:=0 to (x div a[i]) do
                if k<=j then f[i,j]:=max(f[i,j],f[i-1,j-k]+((x-a[i]*k)div b[i]));

    exit(f[n,m]);
End;

Begin
    assign(input,'tiem.in'); reset(input);
    assign(output,'time.out'); rewrite(output);

    readln(n,m);
    for i:=1 to n do
    Begin
        readln(a[i],b[i]);
        if a[i]>maxx then maxx:=a[i];
        if b[i]>maxx then maxx:=b[i];
    End;
    maxx:=maxx*m;
    l:=(m*2)div n;
    r:=maxx;
    while l<=r do
    Begin
        mid:=(l+r)div 2;
        c:=check(mid);
        if c>=m then
        Begin
            r:=mid-1;
            ans:=mid;
        End else l:=mid+1;
    End;
    writeln(ans);

    close(input); close(output);
End.