Знову відкрите казино запропонувало оригінальну гру.

На початку гри круп'є виставляє кілька фішок різних кольорів. Крім того, він повідомляє, які послідовності фішок гравець може забирати собі в процесі гри. Далі гравець забирає собі одну із заздалегідь оголошених послідовностей фішок, розташованих поспіль. Після цього круп'є зсуває фішки, що залишилися, прибираючи розрив. Потім гравець знову забирає собі одну з оголошених послідовностей і таке інше. Гра триває доти, доки гравець може забирати фішки.

Розглянемо приклад. Нехай на столі виставлено ряд фішок rrrgggbbb і круп'є оголосив послідовності rg і gb. Гравець, наприклад, може забрати фішки rg, що лежать на третьому та четвертому місцях зліва. Після цього круп'є зсуне фішки, і на столі вийде ряд rrggbbb. Ще двічі забравши фішки rg, гравець досягне того, що на столі залишаться фішки bbb і гра закінчиться, оскільки гравцеві більше нічого забрати зі столу. Гравець міг би діяти і по-іншому – на другому та третьому ходах забрати не послідовності rg, а послідовності gb. Тоді на столі залишилися б фішки rrb. Аналогічно, гравець міг би досягти того, щоб наприкінці залишилися ряди rrr або rbb.

Після закінчення гри отримані фішки гравець замінює на гроші. Ціна фішки залежить від її кольору.

Потрібно написати програму, яка визначає максимальну суму, яку зможе отримати гравець.

Формат вхідних даних

У першому рядку вхідних даних міститься число \(K\) (\(1 ≤ K ≤ 26\)) — кількість кольорів фішок.

Кожен із наступних \(K\) рядків починається з малої латинської літери, що позначає колір.

Далі в тому ж рядку через пропуск слідує ціле число \(X_i\) (\(1 ≤ X_i ≤ 150\), \(i = 1..K\)) - ціна фішки відповідного кольору.

У (\(K+2\))-му рядку описаний ряд фішок, що лежать на столі на початку гри. Ряд задається \(L\) малими латинськими літерами (\(1 ≤ L ≤ 150\)), які позначають кольори фішок ряду.

Наступний рядок містить число \(N\) (\(1 ≤ N ≤ 150\)) — кількість послідовностей, які були оголошені круп'є.

У наступних \(N\) рядках записані ці послідовності. Гарантується, що сума довжин цих \(N\) рядків не перевищує 150 символів, і всі вони не пусті.

Формат вихідних даних

Виведіть єдине ціле число - максимальну суму грошей, яку може отримати гравець.

Приклад вхідних даних

3
v 3
l 1
u 2
luvu
3
luv
vul
uuu

Приклад вихідних даних

6