#include<iostream>
#include<stdio.h>
#include<algorithm>
#include<queue>
#include<stack>
#include<stdlib.h>
#include<string.h>
#include<math.h>
#define WJ(name) freopen(#name".in","r",stdin);freopen(#name".out","w",stdout);
#define JW fclose(stdin);fclose(stdout);
using namespace std;
int n,m,d[110][3],l,r,b=0,mid,f[110][110];
inline void QR(int& x){
	char ch;
	while(ch=getchar(),ch<'0'||ch>'9');
	x=ch-48;
	while(ch=getchar(),'0'<=ch&&ch<='9')x=x*10+ch-48;
}
inline void QW(int num){
	int cnt=0;char str[30];
	while(str[++cnt]=num%10+48,num/=10);
	while(putchar(str[cnt]),--cnt);
}
int main(){
	WJ(time);
	QR(n),QR(m);
	memset(d,0,sizeof(d));
	for(int i=1;i<=n;i++){
		QR(d[i][1]),QR(d[i][2]);
		b=max(b,max(d[i][1],d[i][2]));
	}
	l=1,r=m*b;
	while(l<=r){
		mid=(l+r)>>1;
		memset(f,-1,sizeof(f));
		f[0][0]=0;
		for(int i=1;i<=n;i++)
			for(int j=0;j<=m;j++)
				for(int k=0;k<=j&&mid>=k*d[i][1];++k)
					if(f[i-1][j-k]<0)continue;
	 				else f[i][j]=max(f[i][j],f[i-1][j-k]+(mid-k*d[i][1])/d[i][2]);
		if(f[n][m]<m)l=mid+1;
		else r=mid-1;
	}
	QW(l);
	JW;
	return 0;
}