记录编号	177627	评测结果	AAAAAAAAAA
题目名称	[NOIP 2010冲刺六]软件开发	最终得分	100
用户昵称	<蒟蒻>我要喝豆奶	是否通过	通过
代码语言	C++	运行时间	0.135 s
提交时间	2015-08-12 15:57:48	内存使用	0.34 MiB

#include<cstdio>
#include<cstring>
#include<fstream>
#include<iostream>
#define fin cin
#define fout cout
#define NL 0
#define LL 1
#define MAXN   1<<7
#define mem memset(f,-0x3f,sizeof(f))
//#define PROGRAM_PAUSE while(1)
#define file_in freopen
#define file_fout freopen
using namespace std;
inline int read(){
char c=getchar();
	int x=0;
	while(c<'0'||c>'9')c=getchar();
	for(;c>='0'&&c<='9';c=getchar())x=x*10+c-'0';
	return x;
}
int n,m,f[MAXN][MAXN],a[MAXN],b[MAXN],L,R,ANS;
bool check(int x);
int main()
{
	#ifndef PROGRAM_PAUSE
		freopen("time.in","r",stdin),freopen("time.out","w",stdout);
	#endif
	#ifdef PROGRAM_PAUSE
		freopen("test.in","r",stdin),freopen("test.out","w",stdout);
	#endif
	#ifndef PROGRAM_PAUSE
		n=read(),m=read();
	#endif
	int T=0;
	for(int i=1;i<=n;i++){
		a[i]=read(),b[i]=read();
		//cin>>a[i]>>b[i];
		R=max(R,a[i]),T=max(T,b[i]);
	}
	R=(R+T)*m;
	while(L<R){
		int mid=(L+R)/2;
		if(check(mid))
			R=mid;
		else
			L=mid+1;
	}
	ANS=R,printf("%d",ANS);
	#ifdef PROGRAM_PAUSE
		PROGRAM_PAUSE;
	#endif
	//#ifndef PROGRAM_PAUSE
	//	getchar();getchar();getchar();
	//#endif
	return (NL);
}

bool check(int x){
	mem;
	f[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(a[i]*(j-k)<=x)	
					f[i][j]=max(f[i][j],f[i-1][k]+(x-a[i]*(j-k))/b[i]);
	if(f[n][m]>=m)
		return LL;
	return NL;

}