记录编号	42749	评测结果	AAAAAAAAAA
题目名称	[NOIP 2010冲刺六]软件开发	最终得分	100
用户昵称	Truth.Cirno	是否通过	通过
代码语言	C++	运行时间	0.057 s
提交时间	2012-09-28 20:26:25	内存使用	1.74 MiB

#include <cstdio>
#include <memory.h>
using namespace std;

int main(void)
{
	freopen("time.in","r",stdin);
	freopen("time.out","w",stdout);
	int i,j,k,n,m,d1[110],d2[110],f[110],l,r,mid,temp;
	bool ok,/*1 added*/ava[110]/*1 added*/;
	scanf("%d%d",&n,&m);
	for (i=1;i<=n;i++)
		scanf("%d%d",&d1[i],&d2[i]);
	l=0;
	r=d1[1]*m+d2[1]*m;
	mid=(l+r)>>1;
	while (l<r)
	{
		memset(f,0,sizeof(f));
		memset(ava,0,sizeof(ava));
		ava[0]=true;
		for (i=1;i<=n;i++)
		{
			temp=mid/d1[i];
			for (j=m;j>=0;j--)
			{
				for (k=0;k<=j&&k<=temp;k++)
				{
					if (ava[j-k]&&f[j]/*2 revised(source:"<")*/<=/*2 revised(source:"<")*/f[j-k]+(mid-k*d1[i])/d2[i])
					{
						f[j]=f[j-k]+(mid-k*d1[i])/d2[i];
						ava[j]=true;
					}
				}
			}
		}
		if (f[m]>=m)
			ok=true;
		else
			ok=false;
		if (ok)
		{
			r=mid;
			mid=(l+r)>>1;
		}
		else
		{
			l=mid+1;
			mid=(l+r)>>1;
		}
	}
	printf("%d\n",mid);
	return(0);
}