记录编号	320602	评测结果	AAAAAAAAAA
题目名称	[NOIP 2010冲刺六]软件开发	最终得分	100
用户昵称	jmisnal	是否通过	通过
代码语言	C++	运行时间	0.102 s
提交时间	2016-10-12 12:53:50	内存使用	0.21 MiB

#include <iostream>
#include <cstdio>
#include <cstring>
using namespace std;
int n,m;
int a[105],b[105];
int f[105][105];//f[i][j]表示前i个人做j个A后还能做最多的B 
int text(int x)
{
//	cout<<x<<endl;
	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;k++)//第i个人可以选择做这么多个 
			{
			//	cout<<i<<' '<<j<<' '<<k<<endl;
				if(x<a[i]*k)continue;
				int B=(x-a[i]*k)/b[i];//做k个剩余的时间可以做B个b。 
				if(f[i-1][j-k]!=-1)
				{
					f[i][j]=max(f[i][j],f[i-1][j-k]+ B );
				}
			}
		}
	}
	return f[n][m];
}
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=1000000;
	while(r-l>1)
	{
		int mid=(l+r)>>1;
	//	cout<<l<<' '<<r<<' '<<mid<<endl; 
		if(text(mid)>=m)
			r=mid;
		else l=mid;
	}
	if(text(r))
		printf("%d\n",r);
	else printf("%d\n",l);
//	cout<<text(18);
	return 0;
}