C++ :

#include<cstdio>
#include<cstring>
#include<cmath>
using namespace std;
int N,M;
int A[201]={0},B[201]={0};
int f[101][101]={0};

int MAX(int x,int y)
{
	if(x<y) return y;
	return x;
}

void Find()
{
	int i,j,k,x;
	int l=1,r=200000,mid;
	
	while(l!=r)
	{
		memset(f,0xff,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])
					{
						x=(mid-k*A[i])/B[i];
						
						if(f[i-1][j-k]>=0){
							f[i][j]=MAX(f[i][j],f[i-1][j-k]+x);
						}
					}
				}
			}
		}
		
		if(f[N][M]>=M)	r=mid;
		else l=mid+1;
	}
	
	printf("%d\n",l);
}


int main()
{
	//freopen("software.in","r",stdin);
	//freopen("software.out","w",stdout);
	
	scanf("%d%d",&N,&M);
	for(int i=1;i<=N;++i)	scanf("%d%d",&A[i],&B[i]);
	
	Find();
	
	return 0;
}