acm International Collegiate Programming Contest

Links

A B C D E F G H

Problem G

映画を観よう

映画好きの栄花さんは,夏休みに映画館に行くことにした.この映画館では,N 種類の映画が,それぞれ一日に一回上映されている.栄花さんの目標は,全種類の映画をなるべく早く見終えることである.

ここで,栄花さんのいる世界では,一日は T 時間からなる.ある日の開始から x 時間 (0 ≤ x ≤ T) 経過した時刻を,その日の x 時と呼ぶ.ある日の T 時は,その翌日の 0 時と同一の時刻である.

この映画館で上映される N 種類の映画のうち,i 番目の映画は,毎日 Si 時からその Di 時間後まで放映される.映画によっては,日をまたいで放映されることもありうる.栄花さんは,それぞれの映画を最初から最後まで継続して視聴しなければならず,一度見始めた映画を途中で見るのをやめたり,上映中の映画を途中から見始めたりすることはできない.また,複数の映画を一度に視聴することもできない.ただし,ある映画の上映終了と同時刻に別の映画が上映開始される場合,それらの映画を連続して視聴することはできる.なお,映画を視聴していない時間帯があっても構わない.

栄花さんは,夏休み初日の 0 時にこの映画館に到着した.ここから栄花さんが映画を視聴する順番を適切に選んだ場合,全 N 種類の映画を見終えるのは,最短で何時間後になるだろうか?なお,0 時に上映開始する映画がある場合,栄花さんは早速その映画を視聴する事が可能である.また,栄花さんは強靭な肉体と精神を持っているため,睡眠や食事などの時間について考慮する必要はない.

Input

入力は 50 個以下のデータセットからなる.各データセットは次の形式で表される.

N T S1 D1 ... SN DN

1 行目には整数 N および T が与えられる.N はこの映画館で上映されている映画の種類数であり,1 ≤ N ≤ 20,000 を満たす.T は栄花さんのいる世界における一日の時間数であり,1 ≤ T ≤ 109 を満たす.

続く N 行には,N 種類の映画の情報が与えられる.このうち i 番目の行には整数 Si および Di が与えられる.Sii 番目の映画の上映開始時刻であり,0 ≤ Si < T を満たす.Dii 番目の映画の上映時間であり,1 ≤ Di ≤ T を満たす.

入力の終わりは 2 つのゼロからなる行で表される.

Output

各データセットに対し,栄花さんが N 種類の映画すべてを見終えるのが,夏休み初日の 0 時から起算して最短で何時間後になるか,一行に出力せよ.

Sample Input

3 24
2 8
10 6
19 5
4 10
0 5
0 3
4 6
9 2
3 1
0 1
0 1
0 1
0 0

Sample Output

24
21
3
(End of Problem G) A B C D E F G H