#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, bool v) { if (v) dat[k / 64] |= 1ull << (k % 64); else dat[k / 64] &= ~(1ull << (k % 64)); } Bitset split(int l, int r) { Bitset result(n); while (l < r && l % 64 != 0) result.set(l, get(l)), l++; while (l < r && r % 64 != 0) r--, result.set(r, get(r)); while (l < r) result.dat[l / 64] = dat[l / 64], l += 64; return result; } Bitset shiftSplit(int l, int r, int k) { Bitset result(n); int d = k / 64, e = k % 64; while (l < r && l % 64 != 0) result.set(l + k, get(l)), l++; while (l < r && r % 64 != 0) r--, result.set(r + k, get(r)); for (int i = r / 64 - 1; i >= l / 64; i--) { result.dat[i + l / 64] = dat[i - d]; result.dat[i + l / 64 + 1] |= (dat[i] >> 63 - e) >> 1; result.dat[i + l / 64] <<= e; } return result; } Bitset operator&(const Bitset &rhs) const { return Bitset(*this) &= rhs; } Bitset operator|(const Bitset &rhs) const { return Bitset(*this) |= rhs; } Bitset operator<<(int k) { return Bitset(*this) <<= k; } Bitset &operator&=(const Bitset &rhs) { for (int i = 0; i < m; i++) dat[i] &= rhs.dat[i]; return *this; } 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, 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; } bool operator[](int k) { return get(k); } }; 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, 1); for (int i = 0; i < n; i++) { dp |= dp.shiftSplit(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; }