202406GESP6级第一题（0分）（dfs)

//#pragma G++ optimize(3)(不用管）
#include<bits/stdc++.h>
using namespace std;
int a[100005],b[25],d=0,n,m,sum;
int dp[100005],ans;
int dfs(int k,int sum,int s){
	if(k==s)return sum;
	if(dp[k]!=0)return dp[k];
	for(int i=1;i<=s;i++){
		if(k+b[i]<=m){
			ans=max(ans,dfs(k+i,sum+b[i],s));
		}
	}
	return dp[k]=ans;
}
int main(){
	cin>>n;
	for(int i=1;i<=n;i++){
		cin>>b[i];
	}
	string s;
	cin>>m>>s;
	int k=0;
	for(int i=2;i<s.size();i++){
		if(s[i]=='c'&&s[i-1]=='b'&&s[i-2]=='a'){
			k++;
		}
		else{
			if(k>=1){
				a[++d]=k;			
			}
			k=0;
		}
	}
	if(k>=1)a[++d]=k;
//	cout<<d<<endl;
	for(int i=1;i<=d;i++){
//		cout<<a[i]<<endl;
		ans=0;
		memset(dp,0,sizeof(dp));
		sum+=dfs(0,0,a[i]);
	}
	cout<<sum;
	return 0;
}