#include #include #include #include #include using namespace std; const int MAXV = 50 * 100000 + 1; mt19937 rng(0x14004); int main() { int n; cin >> n; vector> dp; dp.push_back({0, 0}); vector> jobs; while(n--) { int a, b; cin >> a >> b; jobs.push_back({a, b}); } shuffle(jobs.begin(), jobs.end(), rng); for(auto [a, b]: jobs) { vector> cands, ndp; for(auto [lhs, rhs]: dp) { cands.push_back({lhs + a, rhs}); cands.push_back({lhs, rhs + b}); } sort(cands.begin(), cands.end()); for(auto [lhs, rhs]: cands) { if(ndp.size() && rhs >= ndp.back()[1]) continue; ndp.push_back({lhs, rhs}); } dp.swap(ndp); } int ret = 1e9; for(auto [lhs, rhs]: dp) ret = min(ret, max(lhs, rhs)); cout << ret << "\n"; }