問題文

島1, 島2, ..., 島$N$ が東西方向に並んでいます.
これらの島々の統治者は, すべての島に1体ずつ自らをかたどった銅像を建てることに決めました.

銅像を建てられる職人は $N$ 人存在して, $i$ 番目の職人 (以下職人 $i$ ) は島 $i$ に住んでいます.
統治者が職人 $i$ に対して島 $j$ に銅像を建てるよう依頼するとき, 以下の3種類の費用がかかります.

• 作業費
  • 依頼を行うたびに $a_i$ 円かかります.
• 設計費
  • 初めて職人 $i$ に依頼するときに限り, $b_i$ 円かかります.
• 交通費
  • $i \ne j$ のとき, $|i-j| \times C$ 円かかります.
    

入力

$N \  C$
$a_1\ b_1$
$\vdots$
$a_N\ b_N$

• $1 \le N \le 10^5$
• $1 \le C \le 10^6$
• $1 \le a_i,b_i \le 10^{12}$
• 入力はすべて整数

出力

答えを出力してください. 最後に改行してください.

サンプル

4 2
3 4
2 2
3 2
5 1

18

5 1
1000 1000
1 1
1000 1000
1000 1000
1000 1000

13