假设任务的顺序已经确定，容易得到答案为 \(\max\limits_{i=1}^n\{{sy}_{i-1}+x_i\}\)，其中 \({sy}_k=\sum\limits_{i=1}^ky_i\) 为 \(y\) 的前缀和。特别地，规定 \({sy}_0=0\)。只需要确定任务的最优顺序即可得到答案。
我们断言将所有任务按照 \(x-y\) 降序排序一定不劣。下面给出证明：
考虑相邻的两个任务 \(A:(x_A,y_A)\) 和 \(B:(x_B,y_B)\)，其中 \(x_A-y_A\ge x_B-y_B\)。设任务 \(A\) 之前所有任务的 \(y\) 之和为 \(S\)。
由 \(x_A-y_A\ge x_B-y_B\) 变形得 \(S+y_B+x_A\ge S+y_A+x_B\)。显然，交换任务 \(A\) 与任务 \(B\) 的顺序，只会影响任务 \(A\) 和任务 \(B\) 对最小启动能量值的贡献，对其余任务没有任何影响。容易写出先 \(A\) 后 \(B\) 的贡献为 \(\operatorname{cost}(AB)=\max\{S+x_A,S+y_A+x_B\}\)，先 \(B\) 后 \(A\) 的贡献为 \(\operatorname{cost}(BA)=\max\{S+x_B,S+y_B+x_A\}\)。
有：
\[\begin{aligned}
\operatorname{cost}(AB)&=\max\{S+x_A,S+y_A+x_B\}\\
&\le\max\{S+y_B+x_A,S+y_A+x_B\}\\
&=S+y_B+x_A\\
&\le\max\{S+x_B,S+y_B+x_A\}\\
&=\operatorname{cost}(BA)\\
\end{aligned}
\]
故进行交换一定不优，得证。
只需排序后计算答案即可。时间复杂度 \(O(n\log n)\)。
//By: OIer rui_er
#include <bits/stdc++.h>
#define rep(x, y, z) for(int x = (y); x <= (z); ++x)
#define per(x, y, z) for(int x = (y); x >= (z); --x)
#define debug(format...) fprintf(stderr, format)
#define fileIO(s) do {freopen(s".in", "r", stdin); freopen(s".out", "w", stdout);} while(false)
#define endl '\n'
using namespace std;
typedef long long ll;mt19937 rnd(std::chrono::duration_cast<std::chrono::nanoseconds>(std::chrono::system_clock::now().time_since_epoch()).count());
int randint(int L, int R) {uniform_int_distribution<int> dist(L, R);return dist(rnd);
}template<typename T> void chkmin(T& x, T y) {if(y < x) x = y;}
template<typename T> void chkmax(T& x, T y) {if(x < y) x = y;}template<int mod>
inline unsigned int down(unsigned int x) {return x >= mod ? x - mod : x;
}template<int mod>
struct Modint {unsigned int x;Modint() = default;Modint(unsigned int x) : x(x) {}friend istream& operator>>(istream& in, Modint& a) {return in >> a.x;}friend ostream& operator<<(ostream& out, Modint a) {return out << a.x;}friend Modint operator+(Modint a, Modint b) {return down<mod>(a.x + b.x);}friend Modint operator-(Modint a, Modint b) {return down<mod>(a.x - b.x + mod);}friend Modint operator*(Modint a, Modint b) {return 1ULL * a.x * b.x % mod;}friend Modint operator/(Modint a, Modint b) {return a * ~b;}friend Modint operator^(Modint a, int b) {Modint ans = 1; for(; b; b >>= 1, a *= a) if(b & 1) ans *= a; return ans;}friend Modint operator~(Modint a) {return a ^ (mod - 2);}friend Modint operator-(Modint a) {return down<mod>(mod - a.x);}friend Modint& operator+=(Modint& a, Modint b) {return a = a + b;}friend Modint& operator-=(Modint& a, Modint b) {return a = a - b;}friend Modint& operator*=(Modint& a, Modint b) {return a = a * b;}friend Modint& operator/=(Modint& a, Modint b) {return a = a / b;}friend Modint& operator^=(Modint& a, int b) {return a = a ^ b;}friend Modint& operator++(Modint& a) {return a += 1;}friend Modint operator++(Modint& a, int) {Modint x = a; a += 1; return x;}friend Modint& operator--(Modint& a) {return a -= 1;}friend Modint operator--(Modint& a, int) {Modint x = a; a -= 1; return x;}friend bool operator==(Modint a, Modint b) {return a.x == b.x;}friend bool operator!=(Modint a, Modint b) {return !(a == b);}
};const int N = 1e5 + 5;int n;struct Mission {int x, y;friend bool operator<(Mission a, Mission b) {return a.x - a.y > b.x - b.y;}
}a[N];int main() {ios::sync_with_stdio(false);cin.tie(0); cout.tie(0);cin >> n;rep(i, 1, n) cin >> a[i].x >> a[i].y;sort(a + 1, a + 1 + n);int sum = 0, ans = 0;rep(i, 1, n) {chkmax(ans, sum + a[i].x);sum += a[i].y;}cout << ans << endl;return 0;
}