记录编号	589468	评测结果	AAAAAAAAAA
题目名称	任务	最终得分	100
用户昵称	┭┮﹏┭┮	是否通过	通过
代码语言	C++	运行时间	0.360 s
提交时间	2024-07-05 17:28:02	内存使用	51.91 MiB

#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define db double
#define pii pair<int,int>
#define mp make_pair
#define fi first
#define se second
const int N = 2010,M = 3010;
const ll inf = 1e17;


ll read(){
    ll x = 0,f = 1;char c = getchar();
    for(;c < '0' || c > '9';c = getchar())if(c == '-')f = -1;
    for(;c >= '0' && c <= '9';c = getchar())x = (x<<1) + (x<<3) + c-'0';
    return x * f;
}

int n,ans = INT_MAX;
int f[N][M][2],a[N][2];


int main(){
    freopen("task.in","r",stdin);
    freopen("task.out","w",stdout);
    n = read();
    for(int i = 1;i <= n;i++)a[i][0] = read(),a[i][1] = read();
    memset(f,0x3f,sizeof f);
    f[1][0][0] = f[1][0][1] = 0;
    for(int i = 1;i < n;i++)
        for(int j = 0;j <= 3000;j++)
            for(int p = 0;p <= 1;p++){
                if(a[i][p] >= j){
                    f[i+1][0][p] = min(f[i+1][0][p],f[i][j][p] + a[i][p]);
                    f[i+1][a[i][p] - j][!p] = min(f[i+1][a[i][p] - j][!p],f[i][j][p] + j);
                }
                else{
                    f[i+1][0][!p] = min(f[i+1][0][!p],f[i][j][p] + j);
                    f[i+1][j - a[i][p]][p] = min(f[i+1][j - a[i][p]][p],f[i][j][p] + a[i][p]);
                }
            }
    for(int i = 0;i <= 3000;i++)ans = min(ans,min(f[n][i][0] + max(a[n][0],i),f[n][i][1] + max(a[n][1],i)));
    printf("%d\n",ans);
    
    return 0;
    
}