1 #include <cstdio> 2 #include <cstring> 3 #include <iostream> 4 #define N 100001 5 #define min(x, y) ((x) < (y) ? (x) : (y)) 6 #define max(x, y) ((x) > (y) ? (x) : (y)) 7  8 int n, m, tot, ans; 9 int a[N], b[N], f[N];10 11 inline int read()12 {13     int x = 0, f = 1;14     char ch = getchar();15     for(; !isdigit(ch); ch = getchar()) if(ch == ‘-‘) f = -1;16     for(; isdigit(ch); ch = getchar()) x = (x << 1) + (x << 3) + ch - ‘0‘;17     return x * f;18 }19 20 int main()21 {22     int i, j, tmp;23     n = read();24     memset(f, 127 / 3, sizeof(f));25     for(i = 1; i <= n; i++)26     {27         tot += a[i] = read();28         tot += b[i] = read();29         m += max(a[i], b[i]);30     }31     f[0] = 0;32     for(i = 1; i <= n; i++)33         for(j = m; j >= 0; j--)34         {35             tmp = 1e9;36             if(j >= a[i]) tmp = min(tmp, f[j - a[i]]);37             if(j >= b[i]) tmp = min(tmp, f[j - b[i]] + 1);38             f[j] = tmp;39         }40     for(i = tot >> 1;;i--)41     {42         ans = min(f[i], f[tot - i]);43         if(ans < 1e9)44         {45             printf("%d\n", ans);46             return 0;47         }48     }49 }