#include #define show(x) cout << #x << " = " << x << endl using namespace std; using ll = long long; using pii = pair; using vi = vector; template ostream& operator<<(ostream& os, const vector& v) { os << "sz=" << v.size() << "\n["; for (const auto& p : v) { os << p << ","; } os << "]\n"; return os; } template ostream& operator<<(ostream& os, const pair& p) { os << "(" << p.first << "," << p.second << ")"; return os; } constexpr ll MOD = 1e9 + 7; template constexpr T INF = numeric_limits::max() / 100; constexpr int MAXV = 10000; constexpr int MAXIMUM = 20000; bool check[MAXIMUM + 1]; bool prevcheck[MAXIMUM + 1]; struct House { int v; int t; bool operator<(const House& h) const { return v + t < (h.v + h.t); } }; int main() { int N; cin >> N; vector house(N); for (ll i = 0; i < N; i++) { cin >> house[i].v >> house[i].t; } prevcheck[0] = true; sort(house.begin(), house.end()); prevcheck[house[0].v] = true; ll maxi = house[0].v; for (ll i = 1; i < N; i++) { ll maxi2 = maxi; for (ll j = max(0LL, maxi - house[i].v + 1); j <= min(house[i].t - 1, MAXIMUM - house[i].v); j++) { if (prevcheck[j]) { maxi2 = max(j + house[i].v, maxi2); check[j + house[i].v] = true; } } maxi = maxi2; for (ll j = 0; j <= MAXIMUM; j++) { if (not prevcheck[j]) { prevcheck[j] = check[j]; } check[j] = false; } } for (auto i = MAXIMUM; i >= 0; i--) { if (prevcheck[i]) { cout << i << endl; break; } } return 0; }