レモン王国の勇者ビタロは、ダンジョンを攻略してレベルを上げようとしている。
ダンジョンは 個ある。ダンジョン の難易度は、二つの整数 で表される。現在のレベルが のとき、ダンジョン を攻略すると、次のような結果になる。
一度挑戦したダンジョンには、再び挑戦することはできない。ダンジョンに挑戦する順番と、挑戦するダンジョンの数は自由に決めることができる。
ビタロの現在のレベルは である。ダンジョンを攻略した後に到達できるレベルの最大値を求めよ。
入力は次の形式で与えられる。
1 行目に、ビタロが到達できるレベルの最大値を出力する。
ダンジョンを の順に攻略すると、レベルは順に となる。
| 4 | 38 | 追加の制約はない。 |