救!

#include <bits/stdc++.h>
using namespace std;
const int N=1000;
long long dp[N][N][2];
long long w[N][N],c[N][N],st[N][N],pat[N],p[N][N];
long long n,m,k,aa,bb;
char z;
int main(){
	cin>>n>>m>>k;
	for(int i=1;i<=n;i++){
		for(int j=1;j<=m;j++){
			cin>>w[i][j]>>z;
			if(z=='Y') st[i][j]=1;
		}
	}
	for(int l=1;l<=m;l++){
		for(int h=n;h>=1;h--){
			w[h][l]+=w[h+1][l];
			c[h][l]=c[h+1][l]+1-st[h][l];
		}
	}
	for(int l=1;l<=m;l++){
		for(int v=k;v>=1;v--){
			dp[l][v][0]=dp[l-1][v][0];
			dp[l][v][1]=dp[l-1][v][1];
			for(int h=n;h>=1;h--){
				if(v<c[h][l]){
					break;
			    }
				aa=dp[l-1][v-c[h][l]][0]+w[h][l];
				bb=dp[l-1][v-c[h][l]][1]+w[h][l];
				if(st[h][l]==0){
					dp[l][v][0]=max(aa,dp[l][v][0]);
					dp[l][v][0]=max(bb,dp[l][v][0]);
				}else{
					if(dp[l-1][v-c[h][l]][0])dp[l][v][0]=max(aa,dp[l][v][0]);
					if(bb>dp[l][v][1]){
						p[l][v]=h;
						dp[l][v][1]=bb;
					}
				}
			}
		}
	}
	int vv=k;
	for(int i=m;i>=1;i--){
		pat[i]=p[i][vv];
		vv-=c[pat[i]][i];
	}
	long long res=0;
	for(int i=1;i<=m;i++){
		res+=c[pat[i]][i];
	}
	if(res<k){
		cout<<max(dp[m][k][0],dp[m][k][1])<<endl;
		return 0;
	}
	int kk=0x3f3f3f3f+1,k1=0;
	for(int i=1;i<=m;i++){
		if(pat[i]!=0){
			while(st[pat[i]][i]==1){
				k1+=w[pat[i]][i]-w[pat[i]+1][i]+1;
				pat[i]++;
			}
			kk=min(k1,kk);
		}
	}
	cout<<max(dp[m][k][0],dp[m][k][1]-kk)<<endl;
	return 0;
}