Hanafuda Shuffle

時間制限 : 1 sec, メモリ制限 : 65536 KB
英語版はこちら

Hanafuda Shuffle

カードの山を混ぜて切る方法はいろいろとある. 日本のカード遊びである「花札」における花札混ぜ切りは,札を切る方法の一つ である. 以下に,花札混ぜ切りの方法を示す.

n枚のカードの山がある.図1に示すように,山の一番上からp枚 目の札から連続したc枚の札を抜き取り,それをそのまま山の上に置く. この操作(カット操作という)を繰り返し行う.

花札混ぜ切りをシミュレートし,最終的に山の一番上にくる札を答える プログラムを書きなさい.

Figure 1: Cutting operation

Input

入力は複数のデータセットから構成される.各データセットはnr という二つの正の整数を含む行から始まる.ただし,nは 1 ≤ n ≤ 50であり,rは1 ≤ r ≤ 50である. nrはそれぞれ山にある札の枚数とカット操作の回数を表す.

データセットはさらにr行続く.その各行は1回のカット操作を表して おり,これらの操作は順に実行される. 各行はpcの二つの正の整数を含む. ただし,pcp + cn + 1を 満足している. 札の山の一番上からp枚目の札から,c枚の札を山から抜 き取り,その山の一番上に置く.

入力の終わりは0を二つ含む行によって表される.

各入力行は一つの空白で区切られた二つの整数を含む.行内にその他の文字は ない.

Output

入力の各データセットに対して,最初に一番下を1番として順にn番まで の札が積み上げられた山を仮定して,山を混ぜて切り終わったとき,山の一番 上にある札の番号を出力しなさい.ただし,番号は前後に空白のような余分な文字 を含まないこと.

Sample Input

5 2
3 1
3 1
10 3
1 10
10 1
8 3
0 0

Output for the Sample Input

4
4

Source: ACM International Collegiate Programming Contest , Japan Domestic Contest, Ehime, Japan, 2004
http://www.ehime-u.ac.jp/ICPC/