← 返回题目列表

AtCoder · codefestival_2015_final_h

H. 烤肉大师

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

問題文

A先生是烤肉专家。

A先生 N 肉和长度 我正在尝试用 M 细长的网和木炭来烤肉。肉 i 的长度是 L_i 。网一端坐标 0,另一端坐标 比方说 M 。

最初、肉 i 是坐标 它位于 S_i 。换句话说,网络的坐标 坐标来自 S_i 坐标从 S_i+L_i 肉部分最多 i 已被覆盖。 A先生决定把一些肉去掉,然后在烤架下点燃木炭来烧烤。

烤肉时,肉 2 重叠超过一层的部分将是半熟的。当然,你也不能吃烧烤前去除的肉。

当你仔细选择要去除的肉时,找到可以食用而不会煮过头的部分长度的最大总和。另一种表达可以食用而不会煮过头的部分的长度总和的方法是 1 它等于肉块覆盖的网部分的长度之和。


入力

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

N M
S_1 L_1
S_2 L_2
:
S_N L_N
  • 1 行中,2 整数 给出了 N (1 ≦ N ≦ 10^5), M (1 ≦ M ≦ 10^5) 用空格分隔。这是因为肉 有 N 块,网的长度为 M 。
  • 2 从线 N 行提供肉类信息。其中 i (1 ≦ i ≦ N) 行中,2 整数 给出了 S_i, L_i (0 ≦ S_i < S_i+L_i ≦ M) 用空格分隔。这是第一块肉 i 是坐标 S_i 和肉 i 的长度是 L_i 。

出力

计算可以食用而不会煮过头的部分的长度总和的最大值。 1 行输出。在输出末尾插入换行符。


入力例1

3 7
0 4
3 4
1 5

出力例1

6

下图显示了肉第一次排列时的样子,以及肉第一次排列时的样子。 这显示了当 3 被移除并烘烤时会发生什么。绿色框包围的部分是可以食用而不会煮过头的部分。

figure1

入力例2

8 13
7 2
7 2
1 4
2 5
4 2
11 1
10 1
10 2

出力例2

9