Ромео знає, що Анастасіета дуже CHARівна, і подарунок має бути не менш CHARівний.

В нього є послідовність ~s~, що складається з ~n~ рядків, пронумерованих числами ~1, 2, \dots, n~. Кожен рядок має певну CHARівність, яка дорівнює числу ~a_i~.

Ромео хоче вибрати певну підпослідовність рядків, таку, що жоден вибраний рядок не є префіксом іншого, та сума CHARівностей цих рядків є максимальною.

Рядок ~t~ є префіксом рядка ~s~, якщо ~|t| \le |s|~ та для всіх ~i \in \{1,2,3,\dots,|t|\}~ ~s[i] = t[i]~ (за умови, що символи нумеруються, починаючи з ~1~).

Знайдіть максимальну суму значень ~a_i~ вибраних рядків.

Input

У першому рядку знаходиться одне число ~n~ (~1 \le n \le 2 \cdot 10^5~) — кількість рядків.

У другому рядку знаходяться ~n~ цілих чисел ~a_i~ (~0 \le a_i \le 10^9~) — CHARівності рядків.

У кожному з наступних ~n~ рядків знаходиться один рядок ~s_i~. Кожен рядок складається тільки з малих латинських літер.

Гарантується, що сумарна довжина рядків не перевищує ~5 \cdot 10^5~, тобто ~\sum_{i=1}^{n}|s_i| \le 5 \cdot 10^5~.

Output

Виведіть одне ціле число — максимальну суму вартостей.

Sample Input 1

5
1 2 3 4 5
aa
a
abb
s
aba

Sample Output 1

13

Sample Input 2

4
10 4 3 1
aa
aas
abb
s

Sample Output 2

14