[IOI 2002] 任务安排 2

题目描述

有 $N$ 个任务需要在一台机器上依次执行，任务编号为 $1,2,\ldots,N$，它们的相对顺序不能改变。

你需要将这 $N$ 个任务划分成若干批，每一批都必须由原序列中一段连续的任务组成，并且各批按照任务编号从小到大的顺序依次处理。

机器从时刻 $0$ 开始工作。处理每一批任务之前，机器都需要花费 $S$ 的启动时间。之后，该批中的任务按照原顺序依次执行，其中第 $i$ 个任务本身需要 $T_i$ 的处理时间。

需要注意的是，同一批中的任务虽然是依次处理的，但只有当这一批中的所有任务都处理完毕后，机器才会统一输出这一批所有任务的结果。因此，同一批中所有任务的完成时刻相同。

假设某一批包含任务 $x,x+1,\ldots,y$，并在时刻 $t$ 开始处理，那么这一批中每个任务的完成时刻均为

$t+S+\sum_{i=x}^{y}T_i$。

对于第 $i$ 个任务，给定一个费用系数 $C_i$。若该任务的完成时刻为 $O_i$，则它产生的费用为

$O_i\times C_i$。

一种分组方案的总费用等于所有任务费用之和。请你合理划分这些任务，使得总费用最小，并输出这个最小值。

输入格式

第一行包含一个整数 $N$，表示任务数量。

第二行包含一个整数 $S$，表示每批任务开始处理前所需的启动时间。

接下来 $N$ 行，第 $i$ 行包含两个整数 $T_i,C_i$，分别表示第 $i$ 个任务的处理时间和费用系数。

输出格式

输出一行一个整数，表示能够得到的最小总费用。

样例 1

2
50
100 100
100 100

45000

样例 2

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

153

样例说明

对于样例 2，可以将任务划分为三批：$\{1,2\},\{3\},\{4,5\}$。

各任务的完成时刻分别为 $5,5,10,14,14$，因此对应费用分别为 $15,10,30,42,56$，总费用为 $153$。

数据范围与提示

对于全部数据：

• $1\le N\le 10^4$；
• $0\le S\le 50$；
• $1\le T_i,C_i\le 100$。

保证对于每个测试点，任意一种合法分组方案的总费用均不超过 $2^{31}-1$。