ナップザック復元

string npz_rev(vector<pair<long long,long long>> v,long long m){   
    // ( {重さ、価値} 、重さ制限 )

    // 必要 = A
    // どっちでも = B
    // いらない = C

    long long n = v.size();
    vector<vector<long long>> dp(n,vector<long long>(m+1,-INF));
    dp[0][0] = 0;
    if(v[0].first <= m){
        dp[0][v[0].first] = v[0].second;
    }
    for(long long i = 0;i < n-1;i++){
        for(long long j = 0;j <= m;j++){
            if(dp[i][j]==-INF)continue;
            if(j+v[i+1].first <= m){
            dp[i+1][j+v[i+1].first] = max(dp[i+1][j+v[i+1].first],dp[i][j]+v[i+1].second);
            }
            dp[i+1][j] = max(dp[i+1][j],dp[i][j]);
        }   
    }
    long long maxvalue = 0;
    rep(i,m+1)maxvalue = max(maxvalue,dp[n-1][i]);
    pair<bool,bool> sss = {false,false};
    vector<pair<bool,bool>> ans(n,sss); 
    vector<vector<bool>> ok(n,vector<bool>(m+1,false));
    for(long long i = 0;i <= m;i++){
        if(dp[n-1][i]==maxvalue){
            ok[n-1][i] = true;
        }
    }
    vector<vector<long long>> cnt(n);
    for(long long i = n-1;i > 0;i--){
        for(long long j = 0;j <= m;j++){
            if(!ok[i][j])continue;
            if(dp[i-1][j]==dp[i][j]){
                ans[i].first = true;
                ok[i-1][j] = true;
            }
            if(j - v[i].first < 0)continue;
            if(dp[i-1][j-v[i].first] + v[i].second == dp[i][j]){
                ans[i].second = true;
                ok[i-1][j-v[i].first] = true;
            }
        }
    }
    if(ok[0][0]==true){
        ans[0].first = true;
    }
    if(v[0].first <= m &&  ok[0][v[0].first]){
        ans[0].second = true;
    }
    string ret;
    rep(i,n){
        if(ans[i].first && ans[i].second){
            ret += 'B';
        }
        else if(!ans[i].first && ans[i].second){
            ret += 'A';
        }
        else{
            ret += 'C';
        }
    }
    return ret;
}