まず、値段の合計が \(M\) 円以下となるように選んだ時の価値の合計の最大値を求めます。
これはナップサック問題として知られ、以下のような動的計画法 (DP) によって解くことができます。
\(dp[i][j]\) \((0\leq i\leq N, 0\leq j\leq M)\) を、\(1\) 番目から \(i\) 番目までの商品からいくつか（\(0\) 個でも良い）の商品を値段の合計が \(M\) 円以下となるように選んだ時の価値の合計の最大値として定義します。
\(i=0\) のときは、選ぶ候補となる商品が存在しないため、\(dp[i][j]=0\) となります。 \(i\geq 1\) においては、商品 \(i\) を選ぶ場合と選ばない場合の両方を考慮して、\(dp[i][j]=\max(dp[i-1][j-P_i]+V_i,dp[i-1][j])\) となります。ただし、\(j<P_i\) のときは商品 \(i\) を選ぶことはできないため、単に \(dp[i][j]=dp[i-1][j]\) となります。最終的に、\(dp[N][M]\) が答えとなります。
このようにして得られた答えを \(X\) とします。

次に、商品 \(i\) \((1\leq i\leq N)\) それぞれの分類をどのように判定するかについて考えます。着目すべきは次の \(2\) 点です。

1. 商品 \(i\) を除いた \(N-1\) 個の商品から 、値段の合計が \(M\) 円以下かつ価値の合計が \(X\) となるように商品を選ぶことができるか？
2. 商品 \(i\) を除いた \(N-1\) 個の商品から 、値段の合計が \(M-P_i\) 円以下かつ価値の合計が \(X-V_i\) となるように商品を選ぶことができるか？

ここで、2. の条件は、\(N\) 個の商品から、商品 \(i\) を選びつつ、値段の合計が \(M\) 円以下かつ価値の合計が \(X\) となるように選ぶことができるか？という条件と同値であることに注意してください。

さて、この \(2\) つの条件によって、分類 A,B,C は次のように区別されます。

• 分類 A: 1. の条件をみたさないが、2. の条件をみたす。
• 分類 B: 1. の条件をみたし、2. の条件もみたす。
• 分類 C: 1. の条件をみたすが、2. の条件をみたさない。

それぞれの分類の定義と一致していることは、商品 \(i\) を含む・含まないそれぞれのパターンにおいて、条件（値段の合計が \(M\) 円以下かつ価値の合計が \(X\) ）をみたすような選び方が存在するかどうかに注目して読み替えることで確認できます。なお、1. と 2. どちらもみたさないケースは、\(X\) の定義に反するため、ありえません。

よって、各商品について 1. と2. の条件をみたすかそれぞれ調べれば良いですが、それぞれの商品について愚直に行うと、\(O(N^2M)\) となり間に合いません。 そこで、先ほどの DP を商品を逆順にして行ったものを用意します。すなわち、\(dp2[i][j]\) \((1\leq i\leq N+1, 0\leq j\leq M)\) を、\(i\) 番目から \(N\) 番目までの商品からいくつか（\(0\) 個でも良い）の商品を値段の合計が \(M\) 円以下となるように選んだ時の価値の合計の最大値として定義します。 このとき、商品 \(i\) に対する1., 2. の条件は次のように言い換えられます。

1. \(\displaystyle\max_{0\leq j\leq M}(dp[i-1][j]+dp2[i+1][M-j])\) が \(X\) と等しい。
2. \(\displaystyle\max_{0\leq j\leq M-P_i}(dp[i-1][j]+dp2[i+1][M-P_i-j])\) が \(X-V_i\) と等しい。

dp, dp2 の配列はそれぞれ \(O(NM)\) で用意でき、上記の判定は各 \(i\) \((1\leq i\leq N)\) に対して \(O(M)\) で行うことができます。よって、全体で \(O(NM)\) の時間計算量で行うことができます。 空間計算量についても、64 bit整数型を用いるとして、概算で \(8\) byte \(\times 2\times (N\times M) \sim 800\) MB であるため、メモリ制限の範囲内となっています。

よって、この問題を解くことができました。
なお、空間計算量制限がより厳しい場合は、dp2 を途中まで求めてdp 側を走査するということを繰り返すことで、時間計算量を犠牲にし、それと反比例させる形でメモリ使用量を削減することができます。

C++ による実装例:

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

#define ll long long
#define pll pair<ll,ll>
#define rep(i, n) for(int i = 0; i < n; ++i)
#define N (int)1000
#define M (int)5e+4
#define INF (ll)1e+18


int main(void){
	int n,m,l,r;
	int p[N];
	ll v[N];
	ll dp[N+1][M+1]={};
	ll dp2[N+1][M+1]={};
	ll tgt;
	string ans="";

	cin >> n >> m;
	for(int i=0;i<n;i++)cin >> p[i] >> v[i];

	for(int i=0;i<n;i++){
		for(int j=0;j<=m;j++){
			if(j<p[i])dp[i+1][j]=dp[i][j];
			if(j>=p[i])dp[i+1][j]=max(dp[i][j],dp[i][j-p[i]]+v[i]);
		}
	}

	for(int i=n-1;i>=0;i--){
		for(int j=0;j<=m;j++){
			if(j<p[i])dp2[i][j]=dp2[i+1][j];
			if(j>=p[i])dp2[i][j]=max(dp2[i+1][j],dp2[i+1][j-p[i]]+v[i]);
		}
	}

	tgt=dp[n][m];
	for(int i=0;i<n;i++){
		long long mx_woi=0;
		for(int j=0;j<=m;j++)mx_woi=max(mx_woi,dp[i][j]+dp2[i+1][m-j]);
		long long mx_wi=0;
		for(int j=0;j<=m-p[i];j++)mx_wi=max(mx_wi,dp[i][j]+dp2[i+1][m-p[i]-j]);
		if(mx_woi<tgt)ans+='A';
		else if(mx_wi<tgt-v[i])ans+='C';
		else ans+='B';
	}

	cout<<ans<<endl;

	return 0;
}

C++ による実装例（メモリ使用量を抑えた実装）:

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

#define ll long long
#define rep(i, n) for(int i = 0; i < n; ++i)
#define N (int)1000
#define K (int)100
#define M (int)50000

int main(void){
	int n,m,l,r;
	int p[N];
	ll v[N];
	ll dp[K+1][M+1];
	ll cdp[M+1];
	ll tgt;
	string ans="";
	cin>>n>>m;
	rep(i,n)cin>>p[i]>>v[i];


	rep(j,m+1)cdp[j]=0;
	rep(i,n){
		for(int j=m;j>=p[i];j--)cdp[j]=max(cdp[j],cdp[j-p[i]]+v[i]);
	}
	tgt=cdp[m];
	rep(i,n)ans+='X';

	rep(j,m+1)dp[0][0]=0;
	rep(k,(n-1)/K+1){
		r=n-k*K-1;
		l=max(n-k*K-K,0);
		for(int i=r;i>=l;i--){
			rep(j,M+1){
				dp[r-i+1][j]=dp[r-i][j];
				if(j>=p[i])dp[r-i+1][j]=max(dp[r-i+1][j],dp[r-i][j-p[i]]+v[i]);
			}
		}

		rep(j,m+1)cdp[j]=0;
		rep(i,l){
			for(int j=m;j>=p[i];j--)cdp[j]=max(cdp[j],cdp[j-p[i]]+v[i]);
		}
		for(int i=l;i<=r;i++){
			ll mx_woi=0;
			rep(j,m+1)mx_woi=max(mx_woi,cdp[j]+dp[r-i][m-j]);
			ll mx_wi=0;
			rep(j,m-p[i]+1)mx_wi=max(mx_wi,cdp[j]+dp[r-i][m-p[i]-j]);
			if(mx_woi<tgt)ans[i]='A';
			else if(mx_wi<tgt-v[i])ans[i]='C';
			else ans[i]='B';
			if(i==r)break;
			for(int j=m;j>=p[i];j--)cdp[j]=max(cdp[j],cdp[j-p[i]]+v[i]);
		}
		if(l>0){
			rep(j,M+1)dp[0][j]=dp[K][j];
		}
	}

	cout<<ans<<endl;

	return 0;
}