← 返回题目列表

AtCoder · dwango2016qual_e

E. 烟花

中文机器翻译题面 查看原题

問題文

二王后君很喜欢烟花。今晚二万吾君下班回家时,正在放烟火。

从办公室到二王后君家的路径是一条直线,可以看作是一条数轴。公司坐标是 0 Niwango家的坐标是 L 。

今晚所有的烟花都会燃放 N 它起源于 i(1 ≦ i ≦ N) 第一朵烟花是时候 位于 t_i 它将飞往 P_i(0 ≦ P_i ≦ L) 启动。

二万吾君可以以任意速度下班回家,但他不会回头。不过,您可以中途停下来。

二王后君想尽可能近距离地观看烟花。 因此,对于所有的烟花,二王后君希望使烟花发生时二王后君所在的坐标与烟花将要燃放的坐标之间的差的绝对值之和最小化。

也就是说,二王后君是时候了 坐标为 t 坐标在 f(t) 那么,Niwango-kun 是一个从实数到实数的广义单调递增函数。 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