You are given $N$ strings $S_1, S_2, \ldots, S_N$ consisting of lowercase English letters and $N$ positive integers $A_1, A_2, \ldots, A_N$.

A subset $T$ of $\lbrace 1, 2, \ldots, N \rbrace$ is called a good set if there is no pair $i, j \in T (i \neq j)$ such that $S_i$ is a substring of $S_j$.

Find the maximum possible value of $\displaystyle \sum_{i \in T} A_i$ for a good set $T$.

What is a substring? A substring of a string $S$ is a string obtained by deleting zero or more characters from the beginning and zero or more characters from the end of $S$. For example, `ab` is a substring of `abc`, but `ac` is not a substring of `abc`.

The input is given from Standard Input in the following format:

```
$N$
$S_1$
$S_2$
$\vdots$
$S_N$
$A_1$ $A_2$ $\ldots$ $A_N$
```

Print the answer.

-   $1 \leq N \leq 100$
-   $S_i$ is a string consisting of lowercase English letters.
-   $1 \leq |S_i|$
-   $|S_1| + |S_2| + \ldots + |S_N| \leq 5000$
-   $1 \leq A_i \leq 10^9$

6

The possible good sets T and their corresponding $\sum_{i\in T} A_i$ are as follows:

• $T=\{1\}:\ \sum_{i\in T} A_i=5$
• $T=\{2\}:\ \sum_{i\in T} A_i=2$
• $T=\{3\}:\ \sum_{i\in T} A_i=3$
• $T=\{4\}:\ \sum_{i\in T} A_i=4$
• $T=\{2,3\}:\ \sum_{i\in T} A_i=5$
• $T=\{2,4\}:\ \sum_{i\in T} A_i=6$

The maximum among them is 6, so print 6.