题目描述

A 省有一条东西向的公路经常堵车，为解决这一问题，省政府对此展开了调查。调查后得知，这条公路两侧有很多村落，每个村落里都住着很多个信仰 c 教的教徒，每周日都会开着自家的车沿公路到 B 地去「膜拜」他们的教主，这便是堵车的原因。详细调查显示：这里总共有 $n$ 个村落，并且它们都在 B 地的东边。编号为 $i$ 的村落住有 $r_i$ 个信仰 c 教的教徒，距离 B 地的距离为 $t_i$（单位：公里）。

为解决这一问题，A 省政府决定在这条公路下修建一条地下快速铁路来缓解交通，并沿线修建若干个车站（B 地会修建终点站，不算车站）。每名教徒都会先往 B 地方向开车（如果他所在村庄处恰好有车站就不必开车了），到最近的一个快速铁路车站时换乘（如果直接开到 B 地就不用换乘了），再通过快速铁路到 B 地。

但 A 政府遇到一个难题：修建多少个车站以及在哪修建车站。一个修建车站的方案中，如果修建过多的车站则会花费过多的钱，但修建的车站少了或者修建的位置不对又会导致公路的拥堵。A 政府为了协调这两方面，采用评分的方式来衡量一个方案的好坏（分数越大方案越坏）：每修建一个车站会增加 $m$ 的分数，在某一次「膜拜」中（只考虑去，不考虑返回），每导致 $1$ 个教徒开车行驶 $1$ 公里会增加 $1$ 分。现请你设计一个修建车站的方案，使得分数最小。请输出这个最小的分数。

输入格式

输入的第一行包含两个正整数 $n,m$。之后 $n$ 行每行两个正整数 $t_i,r_i$。

输出格式

输出一个整数，表示最小的分数。

样例输入 #1

4 20
25 3
5 3
25 2
20 5

样例输出 #1

55

样例说明 #1

样例一中，在距 B 地 $20\text{km}$ 处和距 B 地 $25\text{km}$ 处修建车站，$1,3,4$ 号村落里的教徒就不必开车了，得分 $20\times 2=40$ 分。$2$ 号村落里的教徒直接开车到 B 地，得分 $3\times 5=15$ 分。总共得分 $55$ 分。

样例输入 #2

4 30
25 3
5 3
25 2
20 5

样例输出 #2

70

样例说明 #2

样例二中，在距 B 地 $20\text{km}$ 处修建车站，$4$ 号村落里的教徒就不必开车了，得分 $30$ 分。$1$ 号和 $3$ 号村落里的教徒先开车到距 B 地 $20\text{km}$ 处的车站，得分 $3\times 5+2\times 5=25$ 分。$2$ 号村落里的教徒直接开车到 B 地，得分 $3\times 5=15$ 分。总共得分 $70$ 分。

数据规模与约定

对于 $100\%$ 的数据，$n\leq 4\times 10^4$，$m\leq 2\times 10^9$，$t_i\leq 1\times 10^6$，$r_i\leq 1\times 10^3$。

提示：请注意使用 64 位整型存储某些数据和结果。