#codefestival2015finalh. [codefestival_2015_final_h]焼肉の達人

[codefestival_2015_final_h]焼肉の達人

問題文

Aさんは焼肉の達人です。

Aさんは NN 枚の肉と、長さが MM の細長い網と、炭で焼肉をしようとしています。肉 ii の長さは LiL_i です。網の片方の端の座標を 00、もう片方の端の座標を MM とします。

最初、肉 ii は座標 SiS_i の位置に置いてあります。つまり、網の座標 SiS_i から座標 Si+LiS_i+L_i までの区間を肉 ii が覆っていることになります。Aさんは、いくつかの肉を取り除いてから網の下の炭に火をつけて焼くことにしました。

肉を焼くとき、肉が 22 枚以上重なっている部分は生焼けになってしまいます。また、当然ですが焼く前に取り除いた肉は食べられません。

取り除く肉をうまく選んだとき、生焼けにならずに食べられる部分の長さの和の最大値を求めてください。生焼けにならずに食べられる部分の長さの和を別の言い方で表すと、ちょうど 11 枚の肉で覆われた網の区間の長さの和と同じです。


入力

入力は以下の形式で標準入力から与えられる。

NN MM S1S_1 L1L_1 S2S_2 L2L_2 : SNS_N LNL_N

  • 11 行目には、22 つの整数 N(1N105),M(1M105)N (1 ≦ N ≦ 10^5), M (1 ≦ M ≦ 10^5) が空白区切りで与えられる。これは、肉が NN 枚あり、網の長さが MM であることを表す。
  • 22 行目からの NN 行には、肉の情報が与えられる。このうち i(1iN)i (1 ≦ i ≦ N) 行目には、22 つの整数 Si,Li(0Si<Si+LiM)S_i, L_i (0 ≦ S_i < S_i+L_i ≦ M) が空白区切りで与えられる。これは、最初肉 ii が座標 SiS_i に置いてあり、肉 ii の長さが LiL_i であることを表す。

出力

生焼けにならずに食べられる部分の長さの和の最大値を 11 行に出力せよ。出力の末尾に改行を入れること。


入力例1


3 7
0 4
3 4
1 5

出力例1


6

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

figure1


入力例2


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

出力例2


9