[ABC203C] Friends and Travel costs
You cannot submit for this problem because the contest is ended. You can click "Open in Problem Set" to view this problem in normal mode.
[ABC203C] Friends and Travel costs
题面翻译
有个村子排成一行,编号为. 你在第)个村子,可以花费元的代价到达下一个村子。 没有其他的路径可以走。 你最开始在号村子,手上有元。你有个朋友,第个朋友在村子,如果你到了那里,他会给你元。问你最远能到达哪个村子。 不考虑赊账。
题目描述
個の村があり、それぞれ村 , 村 , , 村 と番号がついています。 以上 以下の全ての整数 について、村 で 円を払う事で村 に移動することができます。 それ以外の移動方法はありません。
太郎君は初め 円を持った状態で村 におり、その後、可能な限り大きな番号の村まで進もうとします。 太郎君には 人の友達がいます。 人目の友達は村 にいて、太郎君が村 に着いたときに 円を太郎君に渡します。 太郎君が最終的にたどり着く村の番号を求めてください。
输入格式
入力は以下の形式で標準入力から与えられる。
输出格式
答えを出力せよ。
样例 #1
样例输入 #1
2 3
2 1
5 10
样例输出 #1
4
样例 #2
样例输入 #2
5 1000000000
1 1000000000
2 1000000000
3 1000000000
4 1000000000
5 1000000000
样例输出 #2
6000000000
样例 #3
样例输入 #3
3 2
5 5
2 1
2 2
样例输出 #3
10
提示
制約
- 入力は全て整数である。
Sample Explanation 1
太郎君は以下のように動きます: - 村 から村 へ 円払って移動する。所持金は 円となる。 - 村 から村 へ 円払って移動する。所持金は 円となる。 - 村 で 人目の友達から 円受け取り、所持金は 円となる。 - 村 から村 へ 円払って移動する。所持金は 円となる。 - 村 から村 へ 円払って移動する。所持金は 円となり、この村には友達もいないため村 で止まる。 よって、 を出力します。
Sample Explanation 2
答えが bit 整数に収まらないことがある事に注意してください。
Sample Explanation 3
同じ村に複数の友達がいる可能性もあります。