#P5614. 「一本通 5.6 例 1」任务安排 1

    ID: 4615 传统题 1000ms 512MiB 尝试: 45 已通过: 28 难度: 5 上传者: 标签>难度分类普及+/提高-动态规划线性 DP排序与序列处理一维前缀和CF1700

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

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

题目描述

一台机器要按编号顺序处理 NN 个任务。从时刻 00 开始,机器依次处理若干批任务,每批包含连续的一个或多个任务。

每批都需要启动时间 SS。若一批包含任务 l,l+1,…,rl,l+1,\ldots,r,并在时刻 tt 开始,则这批任务都在时刻 t+S+∑i=lrTit+S+\sum_{i=l}^r T_i 完成。下一批从这个时刻开始处理。

任务 ii 的费用等于其完成时刻乘以费用系数 CiC_i。求所有任务的最小总费用。

输入格式

第一行一个整数 NN。第二行一个整数 SS。

接下来 NN 行,第 ii 行有两个正整数 Ti,CiT_i,C_i,分别表示任务 ii 的处理时间与费用系数。

输出格式

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

样例 1

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

一个最优方案将任务分为三批 {1,2}\{1,2\}、{3}\{3\}、{4,5}\{4,5\},五个任务的完成时刻依次为 5,5,10,14,145,5,10,14,14,总费用为 153153。

数据范围

1≤N≤50001\le N\le5000,0≤S≤500\le S\le50,1≤Ti,Ci≤1001\le T_i,C_i\le100。