Letters and Question Marks

You are given a string $S$ and an array of strings $[t_1, t_2, \dots, t_k]$. Each string $t_i$ consists of lowercase Latin letters from a to n; $S$ consists of lowercase Latin letters from a to n and no more than $14$ question marks.

Each string $t_i$ has its cost $c_i$ — an integer number. The value of some string $T$ is calculated as $\sum\limits_{i = 1}^{k} F(T, t_i) \cdot c_i$, where $F(T, t_i)$ is the number of occurences of string $t_i$ in $T$ as a substring. For example, $F(\text{aaabaaa}, \text{aa}) = 4$.

You have to replace all question marks in $S$ with pairwise distinct lowercase Latin letters from a to n so the value of $S$ is maximum possible.

Input

The first line contains one integer $k$ ($1 \le k \le 1000$) — the number of strings in the array $[t_1, t_2, \dots, t_k]$.

Then $k$ lines follow, each containing one string $t_i$ (consisting of lowercase Latin letters from a to n) and one integer $c_i$ ($1 \le |t_i| \le 1000$, $-10^6 \le c_i \le 10^6$). The sum of lengths of all strings $t_i$ does not exceed $1000$.

The last line contains one string $S$ ($1 \le |S| \le 4 \cdot 10^5$) consisting of lowercase Latin letters from a to n and question marks. The number of question marks in $S$ is not greater than $14$.

Output

Print one integer — the maximum value of $S$ after replacing all question marks with pairwise distinct lowercase Latin letters from a to n.

Examples

input

4
abc -10
a 1
b 1
c 3
?b?

output

5

input

2
a 1
a 1
?

output

2

input

3
a 1
b 3
ab 4
ab

output

8

input

1
a -1
?????????????

output

0

input

1
a -1
??????????????

output

-1

Solution:

#include <bits/stdc++.h>
using namespace std;
#define rep(i,a,n) for (int i=a;i<n;i++)
#define per(i,a,n) for (int i=n-1;i>=a;i--)
#define pb push_back
#define mp make_pair
#define all(x) (x).begin(),(x).end()
#define fi first
#define se second
#define SZ(x) ((int)(x).size())
typedef vector<int> VI;
typedef long long ll;
typedef pair<int,int> PII;
typedef double db;
mt19937 mrand(random_device{}());
const ll mod=998244353;
int rnd(int x) { return mrand() % x;}
ll powmod(ll a,ll b) {ll res=1;a%=mod; assert(b>=0); for(;b;b>>=1){if(b&1)res=res*a%mod;a=a*a%mod;}return res;}
ll gcd(ll a,ll b) { return b?gcd(b,a%b):a;}
// head

int n;

const int AC_SIGMA=14,AC_V=22,AC_N=2010;
struct node {
node *go[AC_V],*fail,*f;
ll fg;
}pool[AC_N],*cur,*root,*q[AC_N];
node* newnode() {
node *p=cur++;
memset(p->go,0,sizeof(p->go)); p->fail=p->f=NULL; p->fg=0;
return p;
}
void init() { cur=pool; root=newnode();}
node* append(node *p,int w) {
if (!p->go[w]) p->go[w]=newnode(),p->go[w]->f=p;
return p=p->go[w];
}
void build() {
int t=1;
q[0]=root;
rep(i,0,t) rep(j,0,AC_SIGMA) if (q[i]->go[j]) {
node *v=q[i]->go[j],*p=v->f->fail;
while (p&&!p->go[j]) p=p->fail;
if (p) v->fail=p->go[j]; else v->fail=root;
q[t++]=q[i]->go[j];
}
rep(i,0,t) if (q[i]->fail) q[i]->fg+=q[i]->fail->fg;
rep(i,0,t) rep(j,0,AC_SIGMA) if (!q[i]->go[j]) {
node *p=q[i]->fail;
if (!p) q[i]->go[j]=root; else q[i]->go[j]=p->go[j];
}
}

int k,go[20][1010];
ll val[20][1010];
char s[401000];
ll dp[(1<<14)+10][1010],tmp[1010];

int main() {
	scanf("%d",&k);
	init();
	rep(i,0,k) {
		scanf("%s",s);
		node *p=root;
		int m=strlen(s);
		rep(j,0,m) p=append(p,s[j]-'a');
		int w;
		scanf("%d",&w);
		p->fg+=w;
}
build();
scanf("%s",s);
int n=strlen(s);
VI qm;
rep(i,0,n) if (s[i]=='?') qm.pb(i);
int m=SZ(qm),g=cur-pool;
rep(S,0,(1<<14)) rep(j,0,g) dp[S][j]=-(1ll<<60);
	dp[0][0]=0;
	/*rep(j,0,g) {
		printf("%d %lld\n",j,pool[j].fg);
		rep(k,0,14) printf("go %d %d %d\n",j,k,pool[j].go[k]-pool);
	}*/
	ll ans=-(1ll<<60);
	rep(pf,0,m+1) {
		int l=(pf==0)?0:qm[pf-1]+1;
		int r=(pf==m)?(n-1):(qm[pf]-1);
		rep(j,0,g) {
			node *p=pool+j;
			ll ss=0;
			rep(k,l,r+1) {
				assert(s[k]!='?');
				p=p->go[s[k]-'a'];
ss+=p->fg;
}
go[pf][j]=p-pool;
val[pf][j]=ss;
}
}
rep(S,0,(1<<14)) {
		int pf=__builtin_popcount(S);
		if (pf>m) continue;
rep(j,0,g) tmp[j]=-(1ll<<60);
		rep(j,0,g) tmp[go[pf][j]]=max(tmp[go[pf][j]],dp[S][j]+val[pf][j]);
		if (__builtin_popcount(S)==m) {
			rep(i,0,g) ans=max(ans,tmp[i]);
		}
		//rep(k,0,g) printf("Tmp %d %d %lld\n",S,k,tmp[k]);
		//rep(k,0,g) printf("Dp %d %d %lld\n",S,k,dp[S][k]);
		rep(j,0,14) if (!(S&(1<<j))) {
			rep(k,0,g) {
				node *p=pool[k].go[j];
				dp[S|(1<<j)][p-pool]=max(dp[S|(1<<j)][p-pool],tmp[k]+p->fg);
}
}
}
printf("%lld\n",ans);
}