记录编号	42762	评测结果	WTTAWTTTTT
题目名称	[NOIP 2010冲刺六]软件开发	最终得分	10
用户昵称	苏轼	是否通过	未通过
代码语言	C++	运行时间	7.004 s
提交时间	2012-09-28 22:15:35	内存使用	2.85 MiB

#include<iostream>
#include<cstdio>
#include<cstdlib>
#include<cmath>
using namespace std;
int n,m,w[105][2]={0};
int q[105][105],answer=0;
int max(int x,int y)
{
    return x>y ? x:y;
}
int main()
{
	freopen ("time.in","r",stdin);
	freopen ("time.out","w",stdout);
	cin>>n>>m;
	for (int i=1;i<=n;i++)
	{
		cin>>w[i][0]>>w[i][1];
	}
	int ans=1;
	while (q[n][m]<=m)
	{
		ans*=2;
		for (int i=0;i<=n;i++)
			for (int j=0;j<=m;j++)
				q[i][j]=-9999;
		/*(for (int i=0;i<=n;i++)
			q[i][0]=0;
			*/
		q[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 (q[i-1][j-k]>=0&&((ans-k*w[i][0])/w[i][1])>=0)
					{
						q[i][j]=max(q[i][j],q[i-1][j-k]+(ans-k*w[i][0])/w[i][1]);
					}
				}
			}
		}
	}
	int ll,rr=0;
	int mid;
	mid=99999999;
	for(int i=1; i<=n; i++)
		mid=mid<w[i][0] ? mid:w[i][0];
		rr+=m*mid+1;
	mid=99999999;
	for(int i=1; i<=n; i++)
		mid=mid<w[i][1] ? mid:w[i][1];
		rr+=m*mid+1;
	ll=1;
	rr=ans;
	while (ll<=rr)
	{
		mid=(ll+rr)/2+1;
		for (int i=0;i<=n;i++)
			for (int j=0;j<=m;j++)
				q[i][j]=-9999;
		/*(for (int i=0;i<=n;i++)
			q[i][0]=0;
			*/
		q[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 (q[i-1][j-k]>=0&&((mid-k*w[i][0])/w[i][1])>=0)
					{
						q[i][j]=max(q[i][j],q[i-1][j-k]+(mid-k*w[i][0])/w[i][1]);
					}
				}
			}
		}
		if (q[n][m]<m)
		{
			rr=mid-1;
		}
		else
		{
			answer=mid;
			ll=mid+1;
		}
	}
	cout<<answer;
	return 0;
}