問題文
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 被移除并烘烤时会发生什么。绿色框包围的部分是可以食用而不会煮过头的部分。
入力例2
8 13 7 2 7 2 1 4 2 5 4 2 11 1 10 1 10 2
出力例2
9