记录编号	333615	评测结果	AAAAAAAAAA
题目名称	1078.[NOIP 2010冲刺六]软件开发	最终得分	100
用户昵称	_Itachi	是否通过	通过
代码语言	C++	运行时间	0.034 s
提交时间	2016-10-31 07:38:08	内存使用	0.33 MiB

#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
const int maxn=105;
int n,m,a[maxn],b[maxn],f[maxn][maxn];
void Rabit_max(int &x,int y){if(x<y)x=y;}
bool Rabit_judge(int sb){
	memset(f,-1,sizeof(f));int i,j,k;
	f[0][0]=0;
	for(i=1;i<=n;i++)f[i][0]=sb/b[i]+f[i-1][0];	
	for(i=1;i<=n;i++)
	for(j=0;j<=m;j++)
	for(k=0;sb>=k*a[i]&&k<=j;k++)
		if(f[i-1][j-k]>-1)
			Rabit_max(f[i][j],f[i-1][j-k]+(sb-k*a[i])/b[i]);
	return f[n][m]>=m;
}
void Rabit_main(){
	scanf("%d%d",&n,&m);int i,l,r,mid;
	for(i=1;i<=n;i++)scanf("%d%d",&a[i],&b[i]);
	l=1,r=(a[1]+b[1])*m;
	while(l^r){
		mid=(l+r)>>1;
		if(Rabit_judge(mid))r=mid;
		else l=mid+1;	
	}
	printf("%d\n",l);
}
int main(){
#define _Rabit _RABIT
#ifdef _Rabit
	freopen("time.in","r",stdin);
	freopen("time.out","w",stdout);
#endif
	Rabit_main();
#ifndef _Rabit
	getchar(),getchar();
#endif
	fclose(stdin);fclose(stdout);
	return 0;
}