Description

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

从零时刻开始，这些任务被分批加工，第 i 个任务单独完成所需的时间为 ti 。在每批任务开始前，机器需要启动时间 s，而完成这批任务所需的时间是各个任务需要时间的总和（同一批任务将在同一时刻完成）。

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

Input Format

第一行一个正整数 n。 第二行是一个整数 s。

下面 n 行每行有一对数，分别为 ti 和 fi​ ，表示第 i 个任务单独完成所需的时间是 ti及其费用系数 fi 。

Output Format

一个数，最小的总费用。

Sample

输入 #1

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

输出 #1

153

Hint

说明/提示 【数据范围】 对于 100% 的数据，1≤n≤5000，0≤s≤50，1≤ti,fi≤100。

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