日刊競プロ ABC 203 -C - Friends and Travel costs-

C - Friends and Travel costs

問題文
10**100+1 個の村があり、それぞれ村 0, 村 1, …, 村 10**100
と番号がついています。0 以上 10**100−1 以下の全ての整数 i について、村 i で 1 円を払う事で村 (i+1) に移動することができます。 それ以外の移動方法はありません。太郎君は初め K 円を持った状態で村 0 におり、その後、可能な限り大きな番号の村まで進もうとします。
太郎君には N 人の友達がいます。i 人目の友達は村 Aii にいて、太郎君が村 Ai にいて、太郎君が村 Ai に着いたときに B i 円を太郎君に渡します。
太郎君が最終的にたどり着く村の番号を求めてください。太郎君が最終的にたどり着く村の番号を求めてください。太郎君が最終的にたどり着く村の番号を求めてください。

制約
1≤N≤2×10**5
1≤K≤10**9
1≤Ai≤10**18
1≤Bi≤10**9
入力は全て整数である。

考えたこと

純粋に予算がなくなるまでにwhile文で回して，予算がなくなるまで違う村に行けば良いと考えた．しかし，この考え方だと入力例２の時にTLEを出してしまう．

村Aiは１つずつ増えていくので，最終的に「太郎くんがたどり着く村の番号」＝「太郎が手にする予算」となり，村Aiに辿り付くためには予算がAiを超えていないといけない．なので，もらえるお金を村の番号順にソートし，現在の予算≧お金がもらえる村の番号の時だけお金をもらえるようにし，N回回すと最終的にもらえるお金がわかり，たどり着ける村の番号がわかる．

N,K = map(int,input().split())
ablist = []
for i in range(N):
 A,B = map(int,input().split())
 ablist.append((A,B))
ablist.sort()
yosan = K
#所持金が到達できる村に対応している
for i in range(N):
 #村Aiに辿り付くためには予算がAiを超えていないといけない
 if yosan>=ablist[i][0]:
   yosan+=ablist[i][1]
print (yosan)

村にたどり着いたらお金がもらえるっていう太郎君何者．．．？

水戸黄門的な．．．？