H - 焼肉の達人

Contest Duration: 2015-11-14 12:45:00+0900 - 2015-11-14 15:45:00+0900 (local time) (180 minutes)

H - 焼肉の達人 Editorial

Time Limit: 2 sec / Memory Limit: 256 MB

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 行に出力せよ。出力の末尾に改行を入れること。

下図はそれぞれ、最初に肉の並べたときの様子、肉 3 を取り除いて焼いたときの様子を表しています。緑の枠で囲った部分が生焼けにならずに食べられる部分となります。