题意同 蓝书-任务安排2， 数据强度有加强

Background

2020年的疫情趋于缓和，空中客车（$AIRBUS$）公司法国图卢兹的总装厂开始组织复工复产
其实本来不用这么麻烦的，可是：，结果：（（（

Description

有 $N$ 架客机排成一个序列在一条生产线上等待总装，它们的总装顺序不得改变。

管理层会把这 $N$ 架客机分成若干批，每一批包含连续的若干架客机。

从时刻 $0$ 开始，客机被分批总装，总装第 $i$ 架客机所需的时间是 $T_i$。

另外，在每批总装开始前，生产线先需要 $S$ 的准备时间，故执行一批总装所需的时间是启动时间 $S$ 加上每架客机的总装所需时间之和。

一架客机的总装执行后，将在生产线上稍作等待，直至该批总装全部执行完毕。

也就是说，同一批任务将在同一时刻完成。

每架客机总装的花费是它的完成时刻（也就是该批总装的完成时刻）乘以一个成本系数 $C_i$。

请为生产线规划一个分组方案，使得总花费最小。

Format

Input

第一行包含整数 $N$。

第二行包含整数 $S$。

接下来N行每行有一对整数，分别为 $T_i$ 和 $C_i$，表示第 $i$ 个任务单独完成所需的时间 $T_i$ 及其费用系数 $C_i$。

Output

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

Sample 1

Input

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

Output

153

Limitation

$1s, 1024KiB$

Hint

$1≤N≤3*10^5,$

$0≤S≤512,$

$1≤Ti,Ci≤512$

Source

$gaomaoqi2022$ 改编自 $AcWing$