批量计划

题目描述:

有N个工作要在一台机器上处理。工作按顺序用1-N处理，形成一个工作序列。工作可以分批处理，每一批含序列中连续一段的工作，但处理顺序不得改变。

每次处理一批工作前，机器需要S的时间初始化。每个工作都有两个属性：成本Fi和处理耗时Ti。假如在t时刻开始处理工作x，x+1，…，x+k则结束时间OverTime=t+S+(T[x]+T[x+1]+…+T[x+k])。该批中每个工作x的代价为Overtime*F[x]，这一批工作的总代价为该批中所有工作的代价总和Overtime*(F[x]+F[x+1]+…+F[x+k])。整个计划的总代价为每批工作的代价和。现在求分批后整个计划的最小总代价。（举例：S = 1, (T₁, T₂, T₃, T₄, T₅) = (1, 3, 4, 2, 1), (F₁, F₂, F₃, F₄, F₅) = (3, 2, 3, 3, 4)，那么假如按{1,2},{3},{4,5}分批，那么每批的结束时间为{5,10,14},每个工作的代价为{15,10,30,42,56},所以整个计划的总代价为153。）

输入格式:

第一行一个整数N，表示工作总数，第二行一个整数S表示机器的初始化时间，接下来N行，第i+2行两个整数Ti,Fi，表示工作i的处理耗时和成本。

输出格式:

一行一个整数Ans表示整个计划的最小总代价，数据保证Ans不超过int范围。

样例输入:

样例1：
2
50
100 100
100 100

样例2：
5
1
1 3
3 2
4 3
2 3
1 4

样例输出:

样例1：
45000

样例2：
153

提示:

1<=N<=10000 1<=S_i, T_i, C_i <=512。

时间限制: 1000ms
空间限制: 256MB

---

来源: ioi2002