#include<iostream>
#include<cstdlib>
#include<cstdio>
#include<cstring>
#include<queue>
using namespace std;
const int maxn = 110 ;
int n,tot,a[maxn],b[maxn],f[maxn][maxn],temp,l,r,mid;
bool Dp(int x)
{
	memset(f,-0x3f,sizeof(f));
	f[0][0]=0;
	for(int i=1;i<=n;i++)
	{
		for(int j=0;j<=tot;j++)
		{
			for(int k=0;k<=j;k++)
			{
				if(x < k * a[i] )continue;
				f[i][j]=max( f[i][j] , f[i-1][j-k] + ( x- k * a[i] ) / b[i] );
			}
		}
	}
	if(f[n][tot]<tot)return false;
	return true;
}
int main()
{
	freopen("time.in","r",stdin);
    freopen("time.out","w",stdout);
	scanf("%d%d",&n,&tot);
	for(int i=1;i<=n;i++){
		scanf("%d%d",&a[i],&b[i]);
		temp=max(temp,max(a[i],b[i]));
	}
	l=1,r=temp*tot*8;
	while(l<r){
		int mid=(l+r)/2;
		if(Dp(mid))r=mid;
		else l=mid+1;
	}
	printf("%d\n",l);
}