记录编号	27435	评测结果	AAAAAAAAAA
题目名称	[IOI 2002] 任务安排	最终得分	100
用户昵称	王者自由	是否通过	通过
代码语言	C++	运行时间	0.021 s
提交时间	2011-09-22 14:52:54	内存使用	0.36 MiB

#include <cstdio>
const int MAXN = 5010,
      INF = 0x7fffffff;
int n, s;
int T[MAXN], F[MAXN];
int f[MAXN], f1[MAXN], f2[MAXN];
int main() {
	freopen("batch.in", "r", stdin);
	freopen("batch.out", "w", stdout);
	scanf("%d %d", &n, &s);
	for(int i=1; i<=n; i++)
		scanf("%d %d", T+i, F+i);
	for(int i=n; i>0; i--) {
		f1[i] = f1[i+1] + T[i];
		f2[i] = f2[i+1] + F[i];
		f[i] = INF;
	}
	for(int i=n; i>0; i--)
		for(int j=i+1; j<=n+1; j++)
			if(f[i] > f[j] + (s + f1[i] - f1[j])* f2[i])
				f[i] = f[j] + (s + f1[i] - f1[j])* f2[i];
	printf("%d\n", f[1]);
	return 0;
}