1 #include <bits/stdc++.h> 2 #define _for(i,a,b) for(int i = (a);i < b;i ++) 3 #define _rep(i,a,b) for(int i = (a);i > b;i --) 4 #define INF 0x3f3f3f3f 5 typedef long long ll; 6 using namespace std; 7 inline ll read() 8 { 9 ll ans = 0; 10 char ch = getchar(), last = ' '; 11 while(!isdigit(ch)) last = ch, ch = getchar(); 12 while(isdigit(ch)) ans = (ans << 1) + (ans << 3) + ch - '0', ch = getchar(); 13 if(last == '-') ans = -ans; 14 return ans; 15 } 16 inline void write(ll x) 17 { 18 if(x < 0) x = -x, putchar('-'); 19 if(x >= 10) write(x / 10); 20 putchar(x % 10 + '0'); 21 } 22 struct P 23 { 24 int a; 25 int b; 26 bool operator < (P se) 27 { 28 return this->b > se.b; 29 } 30 }; 31 int N; 32 P a[203]; 33 int dp[203][203*203]; 34 int sum[203]; 35 int main() 36 { 37 N = read(); 38 _for(i,1,N+1) 39 a[i].a = read(),a[i].b = read(); 40 41 sort(a+1,a+1+N); 42 43 _for(i,1,N+1) 44 sum[i] = sum[i-1]+a[i].a; 45 memset(dp,0x3f,sizeof(dp)); 46 dp[0][0] = 0; 47 _for(i,1,N+1) 48 _for(j,0,sum[i]) 49 { 50 if(j>=a[i].a) 51 dp[i][j] = min(dp[i][j],max(dp[i-1][j-a[i].a],j+a[i].b)); 52 dp[i][j] = min(dp[i][j],max(dp[i-1][j],sum[i]-j+a[i].b)); 53 } 54 int ans = 0x3f3f3f3f; 55 _for(i,0,sum[N]) 56 ans = min(ans,dp[N][i]); 57 write(ans); 58 return 0; 59 }