#P2365. 任务安排

任务安排

题目描述

nn 个任务排成一个序列在一台机器上等待完成(顺序不得改变),这 nn 个任务被分成若干批,每批包含相邻的若干任务。

从零时刻开始,这些任务被分批加工,第 ii 个任务单独完成所需的时间为 tit_i。在每批任务开始前,机器需要启动时间 ss,而完成这批任务所需的时间是各个任务需要时间的总和(同一批任务将在同一时刻完成)。

每个任务的费用是它的完成时刻乘以一个费用系数 fif_i。请确定一个分组方案,使得总费用最小。

输入格式

第一行一个正整数 nn
第二行是一个整数 ss

下面 nn 行每行有一对数,分别为 tit_ifif_i,表示第 ii 个任务单独完成所需的时间是 tit_i 及其费用系数 fif_i

输出格式

一个数,最小的总费用。

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

提示

【数据范围】
对于 100%100\% 的数据,1n50001\le n \le 50000s500 \le s \le 501ti,fi1001\le t_i,f_i \le 100

【样例解释】
如果分组方案是 {1,2},{3},{4,5}\{1,2\},\{3\},\{4,5\},则完成时间分别为 {5,5,10,14,14}\{5,5,10,14,14\},费用 C=15+10+30+42+56C=15+10+30+42+56,总费用就是 153153