记录编号	42558	评测结果	AAAAAAAAAA
题目名称	[NOIP 2010冲刺六]软件开发	最终得分	100
用户昵称	QhelDIV	是否通过	通过
代码语言	C++	运行时间	0.137 s
提交时间	2012-09-26 11:30:40	内存使用	0.51 MiB

#include <fstream>
#include <memory.h>
using namespace std;
ifstream fin("time.in");
ofstream fout("time.out");
int N,M,A[200],B[200],f[200][200];
bool flag[200][200];
void Initialize()
{
int i;
	fin>>N>>M;
	for(i=1;i<=N;i++)
		fin>>A[i]>>B[i];
}

bool dp(int Ch)
{
int i,j,k;
	memset(flag,0,sizeof(flag));
	for(i=1;i<=N;i++)
		for(j=0;j<=M;j++)
			f[i][j]=0;
	for(i=0;i<=N;i++)
		flag[i][0]=true;
	for(i=1;i<=N;i++)
		for(j=0;j<=M;j++)
			for(k=0;k<=j;k++)
				if(Ch>=k*A[i] && flag[i-1][j-k])
				{
					f[i][j]=max(f[i][j],f[i-1][j-k]+(Ch-k*A[i])/B[i]);
					flag[i][j]=true;
				}
	if(f[N][M]>=M)
		return true;
	else
		return false;
}

void Binary()
{
int left=1,right=10000000,mid;
	while(left<right)
	{
		mid=(left+right)/2;
		if(dp(mid))
			right=mid;
		else
			left=mid+1;
	}
	fout<<left<<endl;
}

int main()
{
	Initialize();
	
	Binary();
	
	fin.close();
	fout.close();
	return 0;
}