记录编号	543884	评测结果	AAAAAAAAAAA
题目名称	[NOIP 2010冲刺六]软件开发	最终得分	100
用户昵称	LGLJ	是否通过	通过
代码语言	C++	运行时间	0.036 s
提交时间	2019-10-11 08:05:06	内存使用	1.18 MiB

#include <iostream>
#include <cstring>
#include <cstdio>
#include <vector>
#include <ctime>
#include <stack>
#include <queue>
#include <queue>
#include <cmath>
#include <bitset>
#include <deque>
#include <algorithm>
#include <cctype>
#define I inline
#define R register
#define LL long long
#define INF (0x7f7f7f7f)
#define lowbit(x) (x&(-x))
using namespace std;
int n,m,ans=0;
int num[150][2]={0};
int f[150][150]={0};
I int read()
{
	int x=0;
	char ch=0;
	bool w=true;
	while(!isdigit(ch)){if(ch=='-')w=false;ch=getchar();}
	while(isdigit(ch)){x=(x<<3)+(x<<1)+(ch^48);ch=getchar();}
	return w?x:-x;
}
I bool check(int x)
{
	memset(f,-1,sizeof(f));
	f[0][0]=0;
	for(R int i=1;i<=n;++i)
		for(R int j=0;j<=m;++j)
		{
			f[i][j]=f[i-1][j];
			for(R int k=0;k<=j;++k)
			{
				if((j-k)*num[i][0]>x || f[i-1][k]==-1)
					continue;
				f[i][j]=max(f[i][j],f[i-1][k]+(x-(j-k)*num[i][0])/num[i][1]);
			}
		}
	return f[n][m]>=m;
}
I int MAIN()
{
	freopen ("time.in","r",stdin);
	freopen ("time.out","w",stdout);
	int le=1,ri=0;
	n=read(),m=read();
	for(R int i=1;i<=n;++i)
		for(R int j=0;j<=1;++j)
		{
			num[i][j]=read();
			ri=max(ri,num[i][j]);
		}
	ri*=2*m;
	while(le<ri)
	{
		int mid=(le+ri)>>1;
		if(check(mid))
			ri=mid;
		else
			le=mid+1;
	}
	cout<<le;
	return 0;
}
int lglj=MAIN();
int main(){;}