花火

## 0.前言 前来贡献翻译（改了题目主人公，管理如果不喜那就改回来吧）…… LSY最可爱，逃:)。 --- ## 【题目背景】 烟花升起而后绽放犹如浮生沉浮，一个人孤寂地徘徊…… 所以可爱的LSY很喜欢看烟花。（然而貌似没什么关联） --- ## 【题目描述】 现在LSY在烟花长廊的起点，起点位置为$0$，终点位置为$L$。烟花长廊内总共有$n$束烟花要发射，其中第$i$束烟花要在$t[i]$时在$p[i]$发射。由于LSY十分喜欢烟花，所以LSY在烟花长廊中有非凡的速度使得LSY在$1$秒钟内可以前进任意距离（前进的长度不能为负数但是可以为$0$）。因为LSY视力不是很好，所以某一束烟花在绽放时离她越远的话她的不满值会升高，具体计算方法如下： 如果$t$时刻有一束烟花在$Pf$位置绽放并且LSY在$Pl$位置，那么LSY的不满值会上升$|Pf-Pl|$。 举个栗子：在1时刻，LSY在位置3，有一束烟花在位置4绽放，那么LSY的不满值将会上升1。 现在LSY找到了你，希望你能设计出一个程序使得她看完所有烟花后不满值最小。 --- ## 【输入格式】 第一行两个数$n$，$L$。 接下来有$n$行 第$i$行将会有两个数$t$和$p$表示$t$时刻将会有一束烟花在$p$位置发射。 输入数据保证$t[i]≤t[i+1]$并且如果$t[i]=t[i+1]$那么保证$p[i]≤p[i+1]$。 注意，我们没有理由相信在相同时间相同位置只会发射一束烟花。 --- ## 【输出格式】 一行一个数，表示最小的不满值。 --- ## 【样例输入 1】 ``` 5 10 1 2 1 4 3 8 4 7 5 1 ``` ## 【样例输出 1】 ``` 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 ``` --- ## 【样例解释】 **输入样例 1**： 烟花长廊的长度为$10$，一共有$5$束烟花分别在时间$1$，$1$，$3$，$4$，$5$时在位置$2$，$4$，$8$，$7$，$1$发射。 **输出样例 1**： 在时间$1$时LSY可以移动到位置$3$，这是LSY的不满度将上升$2$，在时间$3$时LSY可以移动到位置$7$，这时LSY的不满度将会上升$1$，第$4$秒时LSY选择不移动，LSY的不满值不会上升，第$5$秒时，LSY的不满值将会上升$6$，最后LSY的总不满值为$9$，第$6$秒时LSY移动至位置$10$，输出$9$，可以证明$9$是最小值。 **输入样例 2**： 有两束烟花在第$1$秒时将同时在位置$4$绽放。 --- 感谢@_YPC 提供的翻译

[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 $ ビット符号付き整数の範囲に収まらない可能性があることに注意すること。 出力の最後には改行を忘れないこと。

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

9

4 10
1 4
1 4
2 1
3 9

3

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

33

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