问题描述

小猫尼万君非常喜欢烟花。今晚，当尼万君从公司回家的时候，正好有烟花大会。

从公司到尼万君家的路是一条直线，可以看作是坐标轴上的数直线。公司的坐标为$0$，尼万君家的坐标为$L$。

今晚要放的烟花一共有$N$发，第$i(1 ≦ i ≦ N)$发烟花在时刻$t_i$在位置$P_i(0 ≦ P_i ≦ L)$放烟花。

尼万君希望尽量靠近烟花观看。因此，尼万君希望通过设置一个宽松单调递增的函数$f(t)$，使得他在每个烟花的打火时间与他所在位置的差的绝对值的和尽可能小。

换句话说，如果尼万君在时刻$t$处于位置$f(t)$，他希望使得对于所有$i$，$|f(t_i)-P_i|$的和尽可能小。

请代替尼万君解决这个问题。

---

输入

输入以以下格式从标准输入给出。

$N$ $L$ $t_1$ $P_1$ . . . $t_N$ $P_N$

• 第一行包含两个整数$N(1 ≦ N ≦ 10^5)$和$L(1 ≦ L ≦ 10^5)$，以空格分隔。
• 接下来的$N$行，每行包含一个整数$t_i(1 ≦ t_i ≦ 10^5)$和$P_i(0 ≦ P_i ≦ L)$，以空格分隔。
• 对于所有$i(1 ≦ i ≦ N-1)$，满足$t_i ≦ t_{i+1}$。如果$t_i = t_{i+1}$，则必须满足$P_i ≦ P_{i+1}$。
• 同一时刻可能有多个位置同时放烟花。

---

部分得分

本问题设有部分得分。

• 如果在满足$N ≦ 2000, L ≦ 2000, t_i ≦ 2000$的数据集上给出正确答案，则可以获得30分。

---

输出

对于每个烟花，输出一个整数，表示尼万君在烟花打火时间所在位置与烟花爆炸位置之间差值的绝对值的总和的最小值。

注意：可以证明这个值是整数。请确保输出的最后有换行符。

---

示例1

5 10
1 2
1 4
3 8
4 7
5 1

输出例1

9

可以通过在时刻1到达位置3，在时刻3到达位置7，和在时刻6到达家的位置10来使得尼万君在烟花打火时间所在位置与烟花爆炸位置之间差值的绝对值的总和为9。不能找到更小的值，因此输出9。

---

示例2

4 10
1 4
1 4
2 1
3 9

输出例2

3

有可能在同时刻、相同位置放烟花。

---

示例3

10 20
2 15
3 4
3 14
4 11
6 0
7 7
8 8
8 8
8 12
9 10

输出例3

33

---