The height of the topmost giant’s head when \(P_N\), i.e. when giant \(i\) is the topmost giant, is \(B_i + \sum_{j \neq i}A_j\).

\(B_i + \sum_{j \neq i}A_j = B_i - A_i + \sum_{j = 1}^{N} A_j\), and the answer is the maximum of this value for \(i = 1,2, \ldots, N\). Since \(\sum_{j = 1}^{N} A_j\) is independent of \(i\), it is sufficient to find \(\max (B_i - A_i)\).

This can be computed using a for loop in a total of \(O(N)\) time.

Sample code

#include <bits/stdc++.h>
using namespace std;
using ll = long long;

int main() {
	int n;
	cin >> n;
	vector<ll> a(n), b(n);
	for (int i = 0; i < n; i++) cin >> a[i] >> b[i];
	ll m = 0;
	for (int i = 0; i < n; i++) m = max(m, b[i] - a[i]);
	ll ans = m;
	for (int i = 0; i < n; i++) ans += a[i];
	cout << ans << '\n';
}