「一本通 5.6 例 3」任务安排 3

题目描述

有 $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$。

一种分组方案的总费用等于所有任务费用之和。

请你合理划分这些任务，使得总费用最小，并输出这个最小值。

需要特别注意的是，虽然 $T_i$ 表示任务的处理时间，但在本题的数据中，$T_i$ 可能为负数。

输入格式

第一行包含两个整数 $N,S$，分别表示任务数量和每批任务开始前所需的启动时间。

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

输出格式

输出一行一个整数，表示所有合法分组方案中最小的总费用。

样例

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

153

样例说明

一种最优的划分方法为：

• 第一批：任务 $1,2$；
• 第二批：任务 $3$；
• 第三批：任务 $4,5$。

三批任务的完成时刻分别为 $5,10,14$，因此各任务的完成时刻为

$5,5,10,14,14$。

对应的费用分别为

$15,10,30,42,56$，

总费用为

$15+10+30+42+56=153$。

因此答案为 $153$。

数据范围与提示

对于全部数据：

• $1\le N\le 3\times10^5$；
• $1\le S\le 2^8$；
• $|T_i|\le 2^8$；
• $0\le C_i\le 2^8$。

特别地，$T_i$ 可能为负数。