#include <stdio.h>
#include <cmath>
#include <algorithm>
#include <cfloat>
#include <stack>
#include <queue>
#include <vector>
#include <string>
#include <iostream>
#include <set>
#include <map>
#include <time.h>
typedef long long int ll;
typedef unsigned long long int ull;
#define BIG_NUM 2000000000
#define MOD 1000000007
#define EPS 0.000000001
using namespace std;


struct Node{
	int children[26],finish_id;
};

struct Data{
	void set(int arg_row,int arg_col,int arg_parent,int arg_node_id){
		row = arg_row;
		col = arg_col;
		parent = arg_parent;
		node_id = arg_node_id;
	}
	int row,col,parent,node_id;
	bool check[4][4];
};

int score[101],num[101],len[101];
int N,index_table[26];
int diff_row[8] = {-1,-1,-1,0,0,1,1,1},diff_col[8] = {-1,0,1,-1,1,-1,0,1};
Node nodes[26][800];

char base_map[4][5];


bool rangeCheck(int row,int col){
	if(row >= 0 && row <= 3 && col >= 0 && col <= 3)return true;
	else{
		return false;
	}
}

void recursive(Data data){

	int adj_row,adj_col,next_node;
	for(int i = 0; i < 8; i++){
		adj_row = data.row+diff_row[i];
		adj_col = data.col+diff_col[i];

		if(rangeCheck(adj_row,adj_col) == false || data.check[adj_row][adj_col] == true)continue;

		next_node = base_map[adj_row][adj_col]-'A';
		if(nodes[data.parent][data.node_id].children[next_node] == -1)continue;

		Data new_data;
		new_data.set(adj_row,adj_col,data.parent,nodes[data.parent][data.node_id].children[next_node]);
		if(nodes[new_data.parent][new_data.node_id].finish_id != -1){
			num[nodes[new_data.parent][new_data.node_id].finish_id]++;
		}
		for(int a = 0; a < 4; a++){
			for(int b = 0; b < 4; b++)new_data.check[a][b] = data.check[a][b];
		}
		new_data.check[adj_row][adj_col] = true;
		recursive(new_data);
	}
}


int main(){

	int N;
	scanf("%d",&N);

	for(int i = 1; i <= N; i++)num[i] = 0;

	for(int i = 0; i < 26; i++)index_table[i] = 1;
	for(int i = 0; i < 26; i++){
		for(int k = 0; k < 800; k++){
			nodes[i][k].finish_id = -1;
			for(int p = 0; p < 26; p++){
				nodes[i][k].children[p] = -1;
			}
		}
	}

	char  buf[9];
	int parent,tmp_index,node_id,length;
	bool FLG;

	for(int i = 1; i <= N; i++){
		scanf("%s %d",buf,&score[i]);
		for(length = 0; buf[length] != '\0';length++);
		len[i]	= length;
		parent = buf[0]-'A';
		tmp_index = 1;
		node_id = 0;
		while(buf[tmp_index] != '\0'){
			if(nodes[parent][node_id].children[buf[tmp_index]-'A'] == -1){
				nodes[parent][node_id].children[buf[tmp_index]-'A'] = index_table[parent]++;
				node_id = nodes[parent][node_id].children[buf[tmp_index]-'A'];
			}else{
				node_id = nodes[parent][node_id].children[buf[tmp_index]-'A'];
			}
			tmp_index++;
		}
		nodes[parent][node_id].finish_id = i;
	}

	for(int row = 0; row < 4; row++)scanf("%s",base_map[row]);
	int T;
	scanf("%d",&T);

	for(int row = 0; row < 4; row++){
		for(int col = 0; col < 4; col++){
			Data new_data;
			new_data.set(row,col,base_map[row][col]-'A',0);
			if(nodes[base_map[row][col]-'A'][0].finish_id != -1){
				num[nodes[base_map[row][col]-'A'][0].finish_id]++;
			}
			for(int a = 0; a < 4; a++){
				for(int b = 0; b < 4; b++)new_data.check[a][b] = false;
			}
			new_data.check[row][col] = true;
			recursive(new_data);
		}
	}


	int dp[T+1],next_dp[T+1];
	dp[0] = 0;
	next_dp[0] = 0;
	for(int i = 1; i <= T; i++){
		dp[i] = -1;
		next_dp[i] = -1;
	}

	for(int word = 1; word <= N; word++){
		if(num[word] == 0)continue;

		for(int i = 1; i <= num[word]; i++){
			for(int k = T; k-i*len[word] >= 0; k--){
				if(dp[k-i*len[word]] >= 0){
					next_dp[k] = max(next_dp[k],dp[k-i*len[word]]+i*score[word]);
				}
			}
		}
		for(int i = 0; i <= T; i++)dp[i] = next_dp[i];
	}

	int maximum = -1;
	for(int i = 0; i <= T; i++)maximum = max(maximum,dp[i]);

	printf("%d\n",maximum);

	return 0;
}

Measured memory_bytes: 5476