#define _USE_MATH_DEFINES #include <cstdio> #include <iostream> #include <sstream> #include <fstream> #include <iomanip> #include <algorithm> #include <cmath> #include <complex> #include <string> #include <vector> #include <array> #include <list> #include <queue> #include <stack> #include <set> #include <map> #include <bitset> #include <numeric> #include <limits> #include <climits> #include <cfloat> #include <functional> #include <iterator> using namespace std; const int MAX = 1000; const int INF = INT_MAX / 2; int main() { int n; cin >> n; vector<int> a(n), b(n); for(int i=0; i<n; ++i) cin >> a[i] >> b[i]; vector<int> dp(n*MAX+1, INF); dp[0] = 0; for(int i=0; i<n; ++i){ vector<int> nextDp(n*MAX+1, INF); for(int j=0; j<=n*MAX; ++j) nextDp[j] = dp[j] + b[i]; for(int j=a[i]; j<=n*MAX; ++j) nextDp[j] = min(nextDp[j], dp[j-a[i]]); dp = move(nextDp); } int ans = INF; for(int i=0; i<=n*MAX; ++i) ans = min(ans, max(i, dp[i])); cout << ans << endl; return 0; }