#codefestival2015finalh. [codefestival_2015_final_h]焼肉の達人
[codefestival_2015_final_h]焼肉の達人
問題文
Aさんは焼肉の達人です。
Aさんは 枚の肉と、長さが の細長い網と、炭で焼肉をしようとしています。肉 の長さは です。網の片方の端の座標を 、もう片方の端の座標を とします。
最初、肉 は座標 の位置に置いてあります。つまり、網の座標 から座標 までの区間を肉 が覆っていることになります。Aさんは、いくつかの肉を取り除いてから網の下の炭に火をつけて焼くことにしました。
肉を焼くとき、肉が 枚以上重なっている部分は生焼けになってしまいます。また、当然ですが焼く前に取り除いた肉は食べられません。
取り除く肉をうまく選んだとき、生焼けにならずに食べられる部分の長さの和の最大値を求めてください。生焼けにならずに食べられる部分の長さの和を別の言い方で表すと、ちょうど 枚の肉で覆われた網の区間の長さの和と同じです。
入力
入力は以下の形式で標準入力から与えられる。
:
- 行目には、 つの整数 が空白区切りで与えられる。これは、肉が 枚あり、網の長さが であることを表す。
- 行目からの 行には、肉の情報が与えられる。このうち 行目には、 つの整数 が空白区切りで与えられる。これは、最初肉 が座標 に置いてあり、肉 の長さが であることを表す。
出力
生焼けにならずに食べられる部分の長さの和の最大値を 行に出力せよ。出力の末尾に改行を入れること。
入力例1
3 7
0 4
3 4
1 5
出力例1
6
下図はそれぞれ、最初に肉の並べたときの様子、肉 を取り除いて焼いたときの様子を表しています。緑の枠で囲った部分が生焼けにならずに食べられる部分となります。
入力例2
8 13
7 2
7 2
1 4
2 5
4 2
11 1
10 1
10 2
出力例2
9