记录编号	320377	评测结果	AAAAAAAAAA
题目名称	[NOIP 2010冲刺六]软件开发	最终得分	100
用户昵称	Magic_Sheep	是否通过	通过
代码语言	C++	运行时间	0.169 s
提交时间	2016-10-11 21:15:04	内存使用	0.27 MiB

#include<cstdio>
#include<iostream>
#include<cstring>
using namespace std;
struct node
{
	int x,y;
};
node t[2005];
int f[125][125],n,m;
inline int DP(int lim)
{
	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 l=0;l<=j;l++)
			{
				if(lim<l*t[i].x) continue;
				int x=(lim-l*t[i].x)/t[i].y;
				if(f[i-1][j-l]>=0)
				{
					f[i][j]=max(f[i][j],f[i-1][j-l]+x);
				}
			}
		}
	}
	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",&t[i].x,&t[i].y);
	}	
	int l=0,r=100010;
	while(l<=r)
	{
		int mid=(l+r)>>1;
		if(DP(mid)>=m) r=mid-1;
		else l=mid+1;
	}
	printf("%d",l);
	return 0;
}