/ 
Time Limit: 2.525 sec / Memory Limit: 246 MB
問題文
ニワンゴくんは花火が大好きです。今夜ニワンゴくんが会社から家に帰るとき、ちょうど花火大会が行われていました。
会社からニワンゴくんの家までの道は直線であり、数直線とみなすことができます。会社の座標は 0 、ニワンゴくんの家の座標は L です。
今夜打ちあがる花火は全部で N 発であり、 i(1 ≦ i ≦ N) 発目の花火は時刻 t_i に位置 P_i(0 ≦ P_i ≦ L) で打ちあがります。
ニワンゴくんは会社から家への道を任意の速度で歩くことができますが、引き返すことはしません。ただし、途中で立ち止まることはできます。
ニワンゴくんは花火をなるべく近くで見たいと思っています。 そのため、ニワンゴくんは、すべての花火に対して、その打ち上げ時刻にニワンゴくんのいる座標と花火の打ちあがる座標の差の絶対値の合計をなるべく小さくしたいです。
すなわち、ニワンゴくんが時刻 t にいる座標を f(t) とすると、ニワンゴくんは実数から実数への広義単調増加な関数 f(t) をうまく設定し、すべての i に対しての |f(t_i)-P_i| の和を小さくしたいです。
ニワンゴくんに代わってこの問題を解いてください。
入力
入力は以下の形式で標準入力から与えられる。
N L t_1 P_1 . . . t_N P_N
- 1 行目には、整数 N(1 ≦ N ≦ 10^5) と L(1 ≦ L ≦ 10^5) が空白を区切りとして与えられる。
- 続く N 行には、 i 番目の花火の打ち上げ時刻と位置を表す整数 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 行に出力せよ。 なお、この値が整数値になることは証明できる。 出力が 32 ビット符号付き整数の範囲に収まらない可能性があることに注意すること。
出力の最後には改行を忘れないこと。
入力例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