#2479. [ABC203C] Friends and Travel costs

    ID: 2479 Type: FileIO (friends) 1000ms 256MiB Tried: 17 Accepted: 7 Difficulty: 8 Uploaded By: Tags>搜索枚举其他数学排序问题分析

[ABC203C] Friends and Travel costs

[ABC203C] Friends and Travel costs

题面翻译

1010010^{100}个村子排成一行,编号为0,1,2,,1010010, 1, 2, \dots, 10^{100}-1. 你在第i(0i<101001i(0 \leq i \lt 10^{100}-1)个村子,可以花费11元的代价到达下一个村子。 没有其他的路径可以走。 你最开始在00号村子,手上有KK元。你有NN个朋友,第ii个朋友在AiA_i村子,如果你到了那里,他会给你BiB_i元。问你最远能到达哪个村子。 不考虑赊账。

题目描述

10100+1 10^{100}+1 個の村があり、それぞれ村 0 0 , 村 1 1 , \ldots , 村 10100 10^{100} と番号がついています。 0 0 以上 101001 10^{100}-1 以下の全ての整数 i i について、村 i i 1 1 円を払う事で村 (i+1) (i+1) に移動することができます。 それ以外の移動方法はありません。

太郎君は初め K K 円を持った状態で村 0 0 におり、その後、可能な限り大きな番号の村まで進もうとします。 太郎君には N N 人の友達がいます。i i 人目の友達は村 Ai A_i にいて、太郎君が村 Ai A_i に着いたときに Bi B_i 円を太郎君に渡します。 太郎君が最終的にたどり着く村の番号を求めてください。

输入格式

入力は以下の形式で標準入力から与えられる。

N N K K A1 A_1 B1 B_1 : : AN A_N BN B_N

输出格式

答えを出力せよ。

样例 #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

提示

制約

  • 1  N  2× 105 1\ \leq\ N\ \leq\ 2\times\ 10^5
  • 1  K  109 1\ \leq\ K\ \leq\ 10^9
  • 1  Ai  1018 1\ \leq\ A_i\ \leq\ 10^{18}
  • 1  Bi  109 1\ \leq\ B_i\ \leq\ 10^9
  • 入力は全て整数である。

Sample Explanation 1

太郎君は以下のように動きます: - 村 0 0 から村 1 1 1 1 円払って移動する。所持金は 2 2 円となる。 - 村 1 1 から村 2 2 1 1 円払って移動する。所持金は 1 1 円となる。 - 村 2 2 1 1 人目の友達から 1 1 円受け取り、所持金は 2 2 円となる。 - 村 2 2 から村 3 3 1 1 円払って移動する。所持金は 1 1 円となる。 - 村 3 3 から村 4 4 1 1 円払って移動する。所持金は 0 0 円となり、この村には友達もいないため村 4 4 で止まる。 よって、 4 4 を出力します。

Sample Explanation 2

答えが 32 32 bit 整数に収まらないことがある事に注意してください。

Sample Explanation 3

同じ村に複数の友達がいる可能性もあります。

Statistics

Related

In following contests:

赛前模拟2

In following homework:

训练题单四