C0934 [SDOI2012]任务安排

内存限制:256 MB 时间限制:1000 ms

题目描述

机器上有 $N$ 个需要处理的任务,它们构成了一个序列。这些任务被标号为 $1$ 到 $N$,因此序列的排列为 $1,2,3...N$。这 $N$ 个任务被分成若干批,每批包含相邻的若干任务。从时刻 $0$ 开始,这些任务被分批加工,第 $i$ 个任务单独完成所需的时间是 $T_i$。在每批任务开始前,机器需要启动时间 $S$,而完成这批任务所需的时间是各个任务需要时间的总和。注意,同一批任务将在同一时刻完成。每个任务的费用是它的完成时刻乘以一个费用系数 $F_i$。请确定一个分组方案,使得总费用最小。

输入格式

第一行两个整数,$N,S$。

接下来 $N$ 行每行两个整数,$T_i,F_i$。

输出

一个整数,为所求的答案。

样例

样例输入 1

5 1 1 3 3 2 4 3 2 3 1 4

样例输出 1

153

提示