3030. 任务安排2
时间限制：1000 MS 内存限制：64 MB
题目描述
# P10979 任务安排 2 ## 题目背景 本题是 P2365 强化版，是 P5785 弱化版，用于让学生循序渐进地了解斜率优化 DP。 ## 题目描述 机器上有 $n$ 个需要处理的任务，它们构成了一个序列。这些任务被标号为 $1$ 到 $n$，因此序列的排列为 $1 , 2 , 3 \cdots n$。这 $n$ 个任务被分成若干批，每批包含相邻的若干任务。从时刻 $0$ 开始，这些任务被分批加工，第 $i$ 个任务单独完成所需的时间是 $T\_i$。在每批任务开始前，机器需要启动时间 $s$，而完成这批任务所需的时间是各个任务需要时间的总和。 **注意，同一批任务将在同一时刻完成**。每个任务的费用是它的完成时刻乘以一个费用系数 $C\_i$。 请确定一个分组方案，使得总费用最小。 ## 输入格式 第一行一个整数 $n$。第二行一个整数 $s$。 接下来 $n$ 行，每行有一对整数，分别为 $T\_i$ 和 $C\_i$，表示第 $i$ 个任务单独完成所需的时间是 $T\_i$ 及其费用系数 $C\_i$。 ## 输出格式 一行，一个整数，表示最小的总费用。 ## 输入输出样例 #1 ### 输入 #1 ``` 5 1 1 3 3 2 4 3 2 3 1 4 ``` ### 输出 #1 ``` 153 ``` ## 说明/提示 对于 $100\%$ 数据，$1 \le n \le 3 \times 10^5$，$1 \le s \le 2^8$，$1\le T\_i \le 2^8$，$0 \le C\_i \le 2^8$。