First, let us consider which village Takahashi can reach. Since Takahashi have to pay \(1\) yen to advance to the next village, in order to reach the village \(M\), the sum of the money that he initially had and he has received from his friend must be at least \(M\).

Since Takahashi can receive at most \((B_1+B_2+\cdots +B_N)\) yen, Takahashi can reach no further than the village \((K+B_1+B_2+\cdots +B_N)\). By the constraint, \(K\leq 10^9,\ B_i\leq 10^9\), and \(N\leq 2\times 10^5\), so \(K+B_1+B_2+\cdots +B_N\leq (2\times 10^5+1)\times 10^9<10^{15}\); particularly, it is less than \(10^{100}\). Therefore, we don’t have to mind the upper bound of \(10^{100}\). Also, we can see that the answer fits in a \(64\)-bit integer. Now, let us find the minimum index of village such that Takahashi has \(0\) yen and no friend.

Suppose that \(A_1\leq A_2\leq \cdots \leq A_N\), which can be achieved by sorting the pairs \((A_i, B_i)\). If \(A_i=A_j\), then \((A_i, B_i)\) and \((A_j, B_j)\) can be in an arbitrary order.

First, if \(K<A_1\), then Takahashi will end up in the village \(K\) before reaching any village with a friend. Next, if \(A_1\leq K\), Takahashi can first reach the village \(A_1\) to receive \(B_1\) yen. Then, if \(K+B_1<A_2\), Takahashi will stuck in the village \((K+B_1)\) before arriving at any other village where the friends live. Otherwise, he can reach the village \(A_2\) and get \(B_2\) yen.

Similarly, we can check if \(K+B_1+\cdots +B_{i-1} < A_i\) for each \(i=1,2,\ldots N\) in the increasing order, and if this holds for some \(i\), he will end up in the village \(K+B_1+\cdots +B_{i-1}\); if \(K+B_1+\cdots +B_{i-1} \geq A_i\) for all \(i\), then he can reach \((K+B_1+\cdots +B_{N} )\), but no further.

If \(i=1\), \(K+B_1+\cdots +B_{i-1}=K\), and for each \(i=2,3,\ldots N\), \(K+B_1+\cdots +B_i =(K+B_1+\cdots +B_{i-1})+B_i\), so for each \(i\), the left hand side can be computed in an \(O(1)\) time, and therefore they can be judged in a total of \(O(N)\) time.

Hence, we can spend \(O(N\log N)\) time for the sort and \(O(N)\) time for the remaining, so that the problem is solved in a total of \(O(N\log N)\), which is fast enough.

Sample code in 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;
}