题目描述

有 $N$ 个任务排成一个序列，等待在一台机器上执行，任务的先后顺序不能改变。机器需要把这 $N$ 个任务分成若干批，每一批包含连续的若干个任务。

执行每一批任务前，机器需要 $S$ 个单位的启动时间。第 $i$ 个任务本身需要 $T_i$ 个单位的执行时间。同一批任务会在这一批全部执行完毕时同时完成。

第 $i$ 个任务的费用等于它的完成时刻乘以费用系数 $C_i$。请确定分批方案，使所有任务的总费用最小。

输入格式

第一行包含两个整数 $N,S$。

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

输出格式

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

样例

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

153

数据范围与提示

• $1 \le N \le 3 \times 10^5$
• $1 \le S \le 2^8$
• $|T_i| \le 2^8$
• $0 \le C_i \le 2^8$
• $T_i$ 可能为负数。

来源

一本通 5.6 例 3