记录编号	177580	评测结果	AAAAAAAAAA
题目名称	[NOIP 2010冲刺六]软件开发	最终得分	100
用户昵称	0	是否通过	通过
代码语言	C++	运行时间	0.131 s
提交时间	2015-08-12 15:22:06	内存使用	0.30 MiB

#include<cstdio>
#include<cstring>

#define MAX(a,b) ((a)>(b)?(a):(b))

using namespace std;

int n,m,f[110][110],a[110],b[110],L,R;

bool check(int x){
	memset(f,-0x3f,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;k++){
				if(a[i]*(j-k)<=x)	
					f[i][j]=MAX(f[i][j],f[i-1][k]+(x-a[i]*(j-k))/b[i]);
			}
		}
	}
	if(f[n][m]>=m)
		return 1;
	return 0;
}

int work(){
	while(L<R){
		int mid=(L+R)/2;
		if(check(mid))
			R=mid;
		else
			L=mid+1;
	}
	return R;
}

int main()
{
	freopen("time.in","r",stdin);
	freopen("time.out","w",stdout);
	scanf("%d%d",&n,&m);
	int t=0;
	for(int i=1;i<=n;i++){
		scanf("%d%d",&a[i],&b[i]);
		if(a[i]>R)
			R=a[i];
		if(b[i]>t)
			t=b[i];	
	}
	R=(R+t)*m;
	int ans=work();
	printf("%d",ans);
}