#include using namespace std; struct Bitset { vector dat; int n, m; Bitset(int n) : n(n), dat((n + 63) / 64 + 1) { m = dat.size() - 1; } int count() { int result = 0; for (int i = 0; i < m; i++) result += __builtin_popcountll(dat[i]); return result; } bool get(int k) { return dat[k / 64] >> (k % 64) & 1ull; } void set(int k) { dat[k / 64] |= 1ull << (k % 64); } void set(int l, int r) { while (l < r && l % 64 != 0) set(l), l++; while (l < r && r % 64 != 0) r--, set(r); while (l < r) dat[l / 64] = ULLONG_MAX, l += 64; } Bitset split(int l, int r) { Bitset result(n); while (l < r && l % 64 != 0) { if (get(l)) result.set(l); l++; } while (l < r && r % 64 != 0) { r--; if (get(r)) result.set(r); } while (l < r) result.dat[l / 64] = dat[l / 64], l += 64; return result; } Bitset operator<<(int k) { Bitset result(*this); result <<= k; return result; } Bitset &operator|=(const Bitset &rhs) { for (int i = 0; i < m; i++) { dat[i] |= rhs.dat[i]; } return *this; } Bitset &operator<<=(int k) { int d = k / 64; int e = k % 64; for (int i = m - 1; i >= d; i--) { dat[i] = dat[i - d]; dat[i + 1] |= (dat[i] >> 63 - e) >> 1; dat[i] <<= e; } for (int i = 0; i < d; i++) dat[i] = 0; return *this; } }; int main() { int n; cin >> n; vector v(n), t(n); vector> vt(n); for (int i = 0; i < n; i++) cin >> v[i] >> t[i], vt[i] = make_tuple(v[i] + t[i], v[i], t[i]); sort(vt.begin(), vt.end()); for (int i = 0; i < n; i++) tie(ignore, v[i], t[i]) = vt[i]; Bitset dp(20202); dp.set(0); for (int i = 0; i < n; i++) { dp |= dp.split(0, t[i]) << v[i]; } int ans = 0; for (int i = 0; i < 20202; i++) if (dp.get(i)) ans = i; cout << ans << endl; return 0; }