#include<cstdio>
#include<cstring>
#include<iostream>
#include<algorithm>
using namespace std;

const int maxn=110;

int N,M;

int A[maxn],B[maxn];

int f[maxn][maxn];//前i个人 做了j个a  

int main()
{	
	freopen("time.in","r",stdin);
	freopen("time.out","w",stdout);
	scanf("%d%d",&N,&M);
	for(int i=1;i<=N;i++)
	scanf("%d%d",&A[i],&B[i]);
	int l=1,r=40000;
	int mid;
	while(l<=r)
	{
		memset(f,-0X3f,sizeof(f));
		f[0][0]=0;
		 mid=(l+r)>>1;
		for(int i=1;i<=N;i++)
		{
			for(int j=0;j<=M;j++)
			{
				for(int k=0;k<=j;k++)
				{
					if(mid-k*A[i]<0)continue;//注意存在不合法的状态，所以
					//我们要把这种情况否掉！ 
					//if(f[i-1][j-k]>0)
					f[i][j]=max(f[i][j],f[i-1][j-k]+(mid-k*A[i])/B[i]);
				}
			}
		}
		if(f[N][M]>=M)r=mid-1;//如果现在能做的b要比M多，那么从理论上来说 MID还可以再小一些！ 
		else l=mid+1;
	}
	printf("%d",l);
 	return 0;
}