https://codeforces.com/gym/102346/problem/E

#include <bits/stdc++.h>
using namespace std;

const int ms = 1e5+5;
const int inf = 0x3f3f3f3f;

int m[ms], f[ms];
int isEmpty[ms];

int dp[3005][3005][2][2];

main() {
  int n;
  cin >> n;
  int qntM = 0;
  for(int i = 0; i < n; i++) {
    cin >> m[i] >> f[i];
    qntM += m[i];
  }
  if(qntM == 0) {
    cout << 0 << '\n';
    return 0;
  }
  int empt = 0;
  for(int i = 0; i < n; i++) {
    if(m[i] == 0 && f[i] == 0) {
      isEmpty[i] = 1;
      empt++;
    }
  }
  for(int i = 0; i < n; i++) {
    if(isEmpty[i]) continue;
    f[i] = f[i] - 1;
  }
  for(int j = 0; j <= empt; j++) {
    dp[n][j][1][1] = 0;
    dp[n][j][0][1] = inf;
    dp[n][j][1][0] = inf;
    dp[n][j][0][0] = inf;
  }
  for(int i = n-1; i >= 0; i--) {
    for(int j = 0; j <= empt; j++) {
      for(int hasSo = 0; hasSo < 2; hasSo++) {
        for(int hasUm = 0; hasUm < 2; hasUm++) {
          int &ans = dp[i][j][hasSo][hasUm];
          ans = dp[i+1][j][hasSo][1] + m[i] + f[i];
          if(isEmpty[i] && j > 0) {
            ans = min(ans, dp[i+1][j-1][1][hasUm]);
          }
          if(!isEmpty[i]) {
            int k = min(j, m[i]); 
            ans = min(ans, dp[i+1][j-k][1][hasUm] + m[i] + m[i] - k);
          }
        }
      }
    }
  }
  cout << dp[0][empt][0][0] << endl;
}

kkk

#include <bits/stdc++.h>
#define N 3003
#define INF 1000000007
using namespace std;
int n, f[N];
struct pool { int m, f; } p[N];
bool cmp1(pool x, pool y) { return x.m + x.f > y.m + y.f; }
bool cmp2(pool x, pool y) { return x.f - x.m > y.f - y.m; }
int main() 
{
    scanf("%d", &n);
    int m = 0;
    bool flag = 1;
    for(int i = 1; i <= n; ++ i) 
    {
        scanf("%d%d", &p[i].m, &p[i].f);
        if(!p[i].m && !p[i].f) ++ m;
        if(p[i].m) flag = 0;
    }
    if(flag) { puts("0"); return 0; }
    sort(p + 1, p + n + 1, cmp1);
    n -= m;
    int sum = 0;
    for(int i = 1; i <= n; ++ i) sum += p[i].m + p[i].f - 1;
    if(!m) 
    {
        sort(p + 1, p + n + 1, cmp2);
        sum -= p[1].f - 1 - p[1].m;
        for(int i = 2; i < n; ++ i)
            if(p[i].f - 1 - p[i].m >= 0) sum -= p[i].f - 1 - p[i].m;
        printf("%d\n", sum);
        return 0;
    }
    for(int i = 1; i <= n; ++ i)
        for(int j = m; j >= p[i].m; -- j) f[j] = max(f[j], f[j - p[i].m] + p[i].f - 1);
    int ans = sum - f[m];
    sum -= m;
    int k = 0;
    for(int i = 1; i <= n; ++ i)
        if(p[i].f - 1 - p[i].m >= 0) sum -= p[i].f - 1 - p[i].m, k += p[i].m;
    if(k >= m) ans = min(ans, sum);
    else 
    {
        f[0] = 0;
        for(int i = 1; i <= m; ++ i) f[i] = -INF;
        for(int i = 1; i <= n; ++ i) if(p[i].f - 1 - p[i].m < 0)
        {
            for(int j = m; j >= 0 && j + p[i].m >= m; -- j) ans = min(ans, sum - f[j] - (p[i].f - 1 - p[i].m));
            for(int j = m; j >= p[i].m; -- j) f[j] = max(f[j], f[j - p[i].m] + p[i].f - 1 - p[i].m);
        }
    }
    printf("%d\n", ans);
    return 0;
}