记录编号	80926	评测结果	AAAAAAAAAA
题目名称	[IOI 2002] 任务安排	最终得分	100
用户昵称	cstdio	是否通过	通过
代码语言	C++	运行时间	0.012 s
提交时间	2013-11-07 22:12:32	内存使用	0.37 MiB

#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cmath>
#include<cstring>
using namespace std;
const int SIZEN=5010;
const int INF=0x7fffffff;
int N,S;
int TS[SIZEN]={0},FS[SIZEN]={0};//时间和费用系数的前缀和
int f[SIZEN]={0};
void DP(void){
	f[N+1]=0;
	int i,j;
	for(i=N;i>=1;i--){
		f[i]=INF;
		for(j=N+1;j>i;j--){
			f[i]=min(f[i],f[j]+(S+TS[j-1]-TS[i-1])*(FS[N]-FS[i-1]));
		}
	}
}
void read(void){
	scanf("%d%d",&N,&S);
	int i;
	for(i=1;i<=N;i++){
		scanf("%d%d",&TS[i],&FS[i]);
		TS[i]+=TS[i-1],FS[i]+=FS[i-1];
	}
}
int main(){
	freopen("batch.in","r",stdin);
	freopen("batch.out","w",stdout);
	read();
	DP();
	printf("%d\n",f[1]);
	return 0;
}