まず、高橋君がたどりつける村がみたす条件について考えます。 太郎君が次の村に進むためには必ず \(1\) 円払う必要があるので、村 \(M\) にたどりつくためには、最初に持っているお金とそれまでに友人からもらったお金が \(M\) 円以上である必要があります。

高橋君がもらえるお金は最大 \((B_1+B_2+\cdots +B_N)\) 円であるので、この事から 高橋君は最大でも村 \((K+B_1+B_2+\cdots +B_N)\) までしか到達できない事が分かります。 制約より、 \(K\leq 10^9,\ B_i\leq 10^9,\ N\leq 2\times 10^5\) であるので \(K+B_1+B_2+\cdots +B_N\leq (2\times 10^5+1)\times 10^9<10^{15}\) であり、特に \(10^{100}\) より小さいです。 よって \(10^{100}\) の上限は考えなくて良い事が分かります。 また、答えが \(64\) bit 整数におさまる事も分かります、 以下、高橋君の所持金が \(0\) 円となり友達もいないような最小の村の番号を求める事を考えます。

いま、\(A_1\leq A_2\leq \cdots \leq A_N\) が満たされているとします。 \((A_i, B_i)\) をペアにしてソートする事でこのような状態にすることができます。\(A_i=A_j\) であるようなものについては \((A_i, B_i)\) と \((A_j, B_j)\) のどちらが先に来ても構いません。

まず, \(K<A_1\) のとき、高橋君は友達のいるどの村にたどり着く前に村 \(K\) で動けなくなってしまいます。次に、 \(A_1\leq K\) のとき、まず高橋君は村 \(A_1\) に到達し \(B_1\)円をもらう事が出来ます。この後、\(K+B_1<A_2\) ならば他の友達がいる村にたどり着く前に村 \((K+B_1)\) で動けなくなってしまいます。そうでないとき、さらに村 \(A_2\) に到達しさらに \(B_2\) 円をもらう事が出来ます。

これを繰り返すと、 \(i=1,2,\ldots N\) について昇順に \(K+B_1+\cdots +B_{i-1} < A_i\) であるかを調べ、ある \(i\) についてこれが成り立つならば村 \(K+B_1+\cdots +B_{i-1}\) で動けなくなり、どの \(i\) についても \(K+B_1+\cdots +B_{i-1} \geq A_i\) ならば村 \((K+B_1+\cdots +B_{N} )\) まで進め、そこで動けなくなる事が分かります。

\(i=1\) においては \(K+B_1+\cdots +B_{i-1}=K\) であり、さらに \(i=2,3,\ldots N\) について \(K+B_1+\cdots +B_i =(K+B_1+\cdots +B_{i-1})+B_i\) であることに注意すると各 \(i\) について左辺を\(O(1)\)で計算することができ、全体で \(O(N)\)で判定することができます。

よって、ソートに \(O(N\log N)\) 、その後の処理に \(O(N)\) であり、この問題は \(O(N\log N)\) で解け、十分高速です。

C++による実装例:

#include<bits/stdc++.h>

using namespace std;

int main(void) {
	int n;
	long long k;
	long long x, y;
	vector<pair<long long, long long> >a;

	cin >> n >> k;
	for (int i = 0; i < n; i++) {
		cin >> x >> y;
		a.push_back({ x,y }); //a[i].first=A_i, a[i].second=B_i
	}

	sort(a.begin(), a.end());
	for (int i = 0; i < n; i++) {
		if (a[i].first > k)break;
		k += a[i].second;
	}
	cout << k << endl;
	return 0;
}