#include <assert.h>
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <ctype.h>
#include <time.h>
const int INF = -2000000000;
int Wl;
int dp[16384];
int small[1024];
int wl[1024];
int maxJ;
int j, k, x, y, X, Y, flag;
int main(int argc, char** argv){
int answer = -1;
int N;
static int v[1000];
static char w[1000][10+1];
static char W[10000+1];
char* problem_file;
clock_t start, end;
FILE* fp;
int i;
char buf[0xffff];
char* p;
if(argc <= 1){
fprintf(stderr, "Enter the input file.\n");
exit(EXIT_FAILURE);
}
problem_file = argv[1];
fp = fopen(problem_file, "r");
if(fp == NULL){
fprintf(stderr, "Cannot open %s.\n", problem_file);
exit(EXIT_FAILURE);
}
p = fgets(buf, 0xffff, fp);
assert(p != 0);
N = atoi(strtok(buf, " \n"));
assert(1 <= N && N <= 1000);
p = fgets(buf, 0xffff, fp);
assert(p != 0);
p = strtok(buf, " \n");
strcpy(W, p);
assert(1 <= strlen(W) && strlen(W) <= 10000);
for(p = W; *p; ++p){
assert(islower(*p));
}
for(i = 0; i < N; ++i){
p = fgets(buf, 0xffff, fp);
assert(p != 0);
v[i] = atoi(strtok(buf, " "));
assert(-1000000 <= v[i] && v[i] <= 1000000);
p = strtok(NULL, " \n");
strcpy(w[i], p);
assert(1 <= strlen(w[i]) && strlen(w[i]) <= 10);
for(p = w[i]; *p; ++p){
assert(islower(*p));
}
}
fclose(fp);
start = clock();
maxJ = 0;
Wl = strlen(W);
dp[0]=0;
for(i = 0; i < N; ++i){
wl[i] = strlen(w[i]);
}
for(i = 1; i < 16384; ++i){
dp[i] = INF;
}
for(i = 1; i < 1024; ++i){
small[i] = INF;
}
for(i = 0; i < N; ++i){
for(j = maxJ; j >= 0; --j){
if(dp[j] != INF){
flag = 1;
for(k = 0; k < wl[i]; ++k){
x = j+k;
X = W[x];
Y = w[i][k];
if( Wl <= x )goto A;
if( X < Y )goto A;
if( X > Y ){
flag = 0;
break;
}
}
y = dp[j] + v[i];
if(flag){
x = j+wl[i];
if(dp[x] < y){
dp[x] = y;
if(maxJ < x){
maxJ = x;
}
}
}else{
if(small[i] < y){
small[i] = y;
}
}
}
A:;
}
}
for(i = 0; i <= maxJ; ++i){
if(answer < dp[i]){
answer = dp[i];
}
}
x = 0;
for(i = 0; i < N; ++i){
y = 0;
if(small[i] != 0){
y = small[i];
for(j = i+1; j < N; ++j){
if(v[j] > 0)y += v[j];
}
if(x < y)x=y;
}
}
if(answer < x)
answer = x;
end = clock();
printf("%s, %f, %d\n", problem_file, (double)(end - start) / CLOCKS_PER_SEC, answer);
printf("%s, %d\n", problem_file, answer);
return 0;
}