#P10979. 任务安排 2

任务安排 2

题目背景

本题是 P2365 强化版,是 P5785 弱化版,用于让学生循序渐进地了解斜率优化 DP。

题目描述

机器上有 nn 个需要处理的任务,它们构成了一个序列。这些任务被标号为 11nn,因此序列的排列为 1,2,3n1 , 2 , 3 \cdots n。这 nn 个任务被分成若干批,每批包含相邻的若干任务。从时刻 00 开始,这些任务被分批加工,第 ii 个任务单独完成所需的时间是 TiT_i。在每批任务开始前,机器需要启动时间 ss,而完成这批任务所需的时间是各个任务需要时间的总和。

注意,同一批任务将在同一时刻完成。每个任务的费用是它的完成时刻乘以一个费用系数 CiC_i

请确定一个分组方案,使得总费用最小。

输入格式

第一行一个整数 nn。第二行一个整数 ss

接下来 nn 行,每行有一对整数,分别为 TiT_iCiC_i,表示第 ii 个任务单独完成所需的时间是 TiT_i 及其费用系数 CiC_i

输出格式

一行,一个整数,表示最小的总费用。

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

提示

对于 100%100\% 数据,1n3×1051 \le n \le 3 \times 10^51s281 \le s \le 2^81Ti281\le T_i \le 2^80Ci280 \le C_i \le 2^8