ABC F WA 求条

#include<bits/stdc++.h>
using namespace std;
const int N=1e3+10,M=5e4+10;
typedef long long ll;
int n,m,p[N],v[N];ll ans,dp1[N][M],dp2[N][M];
char c[N];
int main() {
    ios::sync_with_stdio(0);
    cin.tie(0),cout.tie(0);
    cin>>n>>m;
    for(int i=1;i<=n;i++){
    	cin>>p[i]>>v[i];
	}
    for(int i=1;i<=n;i++){
    	for(int j=m;j>=p[i];j--){
    		dp1[i][j]=max(dp1[i-1][j],dp1[i-1][j-p[i]]+v[i]);
		}
	}
    for(int j=m;j>=0;j--)ans=max(ans,dp1[n][j]);
    for(int i=n;i>=1;i--){
    	for(int j=m;j>=p[i];j--){
    		dp2[i][j]=max(dp2[i+1][j],dp2[i+1][j-p[i]]+v[i]);
		}
	}
	for(int i=1;i<=n;i++){
    	for(int j=0;j<=m;j++){
    		dp2[i][j]=max(dp2[i][j-1],dp2[i][j]);
		}
	}
	for(int i=1;i<=n;i++){
		ll noi=0;
		for(int j=0;j<=m;j++){
			noi=max(noi,dp1[i-1][j]+dp2[i+1][m-j]);
		}
		ll havi=0;
		for(int j=0;j<=m-p[i];j++){
			havi=max(havi,dp1[i-1][j]+dp2[i+1][m-p[i]-j]+v[i]);
		}
		if(noi<ans){
            c[i-1]='A';
        }
		else if(havi<ans){
            c[i-1]='C';
        }
		else c[i-1]='B';
	}
    cout<<c;
    return 0;
}