AT_dwango2016qual_e 花火

[problemUrl]: https://atcoder.jp/contests/dwango2016-prelims/tasks/dwango2016qual_e ニワンゴくんは花火が大好きです。今夜ニワンゴくんが会社から家に帰るとき、ちょうど花火大会が行われていました。 会社からニワンゴくんの家までの道は直線であり、数直線とみなすことができます。会社の座標は $ 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} $ を満たす。 - 同じ時刻に、同じ位置で花火が打ちあがることもある。

すべての花火に対して、その打ち上げ時刻にニワンゴくんがいる座標と花火の打ちあがる座標の差の絶対値の総和の最小値を $ 1 $ 行に出力せよ。 なお、この値が整数値になることは証明できる。 出力が $ 32 $ ビット符号付き整数の範囲に収まらない可能性があることに注意すること。 出力の最後には改行を忘れないこと。

### 部分点 この問題には部分点が設定されている。 - $ N\ ≦\ 2000,\ L\ ≦\ 2000,\ t_i\ ≦\ 2000 $ を満たすデータセットに正解した場合、部分点として $ 30 $ 点が与えられる。 ### Sample Explanation 1 時刻 $ 1 $ に座標 $ 3 $ へ、時刻 $ 3 $ に座標 $ 7 $ へ、時刻 $ 6 $ に家のある座標 $ 10 $ に移動することで、打ち上げ時刻にニワンゴくんがいる座標と花火の打ちあがる座標の差の絶対値の総和を $ 9 $ にすることができます。それより小さい値にすることはできないので、 $ 9 $ を出力します。 ### Sample Explanation 2 同時に、同じ座標で花火が打ちあがることもあります。