Andi is getting married! He and his partner plan to have $N$ children. To avoid any hassle in the future, Andi wants to decide all their children's name in advance. Specifically, he wants each child to have a name which is lexicographically *larger* than any of his/her older siblings. Of course, his partner also agrees with this idea. String $A$ is lexicographically larger than string $B$ if and only if $B$ is a prefix of $A$ or there exists an index $i$ where $A_i > B_i$ and $A_j = B_j$ for all $j < i$. Note that a proper name can be as short as one character, but it *cannot* be an empty string.
Life is good for Andi, until one day he told his soon-to-be-grandmother-in-law (i.e. his partner's grandma) about this marriage plan. After learning that Andi plans to have $N$ children with her granddaughter, she gave him $N$ names to be used. Moreover, the $i^(t h)$ name can only be used for the $i^(t h)$ child.
After going through a long debate with her grandma, Andi came into an agreement: The $i^(t h)$ child's name should be a subsequence of the $i^(t h)$ name her grandma gave. A string $A$ is a subsequence of string $B$ if $A$ can be obtained by deleting zero or more characters from $B$ without changing the remaining characters' order, e.g., _ABC_ is a subsequence of _DAEBCCB_, but _EFG_ is not a subsequence of _FABEGC_.
Even though Andi dislikes the given list of names, he still wants to impress his partner by showing that he can satisfy both her grandma's wish and his own desire (i.e. each child's name is lexicographically larger than any of his/her older siblings). However, Andi wonders, what is the maximum possible total length of their children names?
For example, let $N = 3$, and the names given by his partner's grandma are $($_KARIM_$,$ _PARBUDI_$,$ _CHANDRA_$)$. Here are several example set of names which satisfies Andi's desire:
Input begins with a line containing an integer $N$ ($1 <= N <= 15$) representing the number of children. The next $N$ lines, each contains a string $S_i$ ($1 <= | S_i | <= 15$) representing the $i^(t h)$ name given by Andi's soon-to-be-grandmother-in-law. $S_i$ contains only uppercase alphabets ($S_{i j} in {A -Z}$).
Output contains an integer in a line representing the maximum possible total length of their children names, or _-1_ if no possible valid set of names can be obtained.
_Explanation for the sample input/output #3_
One possible solution is $[ texttt(A V E), texttt(F U N), texttt(I N), texttt(I P C), texttt(J A K A R T A), texttt(N T Y), texttt(T E E N) ]$ with a total length of $3 + 3 + 2 + 3 + 7 + 3 + 4 = 25$.
## Input
Input begins with a line containing an integer $N$ ($1 <= N <= 15$) representing the number of children. The next $N$ lines, each contains a string $S_i$ ($1 <= | S_i | <= 15$) representing the $i^(t h)$ name given by Andi's soon-to-be-grandmother-in-law. $S_i$ contains only uppercase alphabets ($S_{i j} in {A -Z}$).
## Output
Output contains an integer in a line representing the maximum possible total length of their children names, or _-1_ if no possible valid set of names can be obtained.
[samples]
## Note
_Explanation for the sample input/output #3_One possible solution is $[ texttt(A V E), texttt(F U N), texttt(I N), texttt(I P C), texttt(J A K A R T A), texttt(N T Y), texttt(T E E N) ]$ with a total length of $3 + 3 + 2 + 3 + 7 + 3 + 4 = 25$.
**Definitions**
Let $ T \in \mathbb{Z} $ be the number of test cases.
For each test case:
- Let $ m \in \mathbb{Z} $ be the contest duration.
- Let $ n \in \mathbb{Z} $ be the number of clarifications.
- Let $ k \in \mathbb{Z} $ be the number of clarification types.
- Let $ C = \{(t_i, p_i) \mid i \in \{1, \dots, n\}\} $ be the set of clarifications, where $ t_i \in \{1, \dots, m\} $ is the send time and $ p_i \in \{1, \dots, k\} $ is the type.
For each type $ j \in \{1, \dots, k\} $, define:
- $ s_j = \min\{t_i \mid p_i = j\} $: the first time a clarification of type $ j $ was sent.
- $ c_j = |\{i \mid p_i = j\}| $: the total count of clarifications of type $ j $.
**Constraints**
1. $ 1 \le T \le 256 $
2. For each test case:
- $ 1 \le m \le 10^5 $, $ 1 \le k \le n \le 10^5 $
- $ 1 \le t_i \le m $, $ 1 \le p_i \le k $
- Each type $ j \in \{1, \dots, k\} $ appears at least once.
3. Total sum of $ m $ and $ n $ across all test cases $ \le 3 \times 10^6 $
**Objective**
Minimize the earliest time $ F $ at which all clarifications are answered, under the rules:
- KAN must answer the *first* clarification of each type $ j $ at or after time $ s_j $.
- Hasan may answer clarifications of type $ j $ only at times $ \ge x + 1 $, where $ x $ is the time KAN answered the first clarification of type $ j $.
- Each of KAN and Hasan can answer at most one clarification per minute.
- Clarifications may be answered in any order, but not before they are sent.
Let $ A_j $ be the time KAN answers the first clarification of type $ j $, with $ s_j \le A_j \le m $.
Let $ B_j $ be the total number of clarifications of type $ j $ answered by Hasan. Then $ c_j = 1 + B_j $.
The total time to answer all clarifications of type $ j $ is at least $ 1 + B_j $ minutes, starting no earlier than $ A_j $ for Hasan and $ A_j $ for KAN’s first.
The schedule must fit within a timeline where at each minute $ \tau $, at most one clarification is answered by KAN and at most one by Hasan.
**Goal**: Find the minimal $ F \in \mathbb{Z} $ such that there exists an assignment of answer times to all $ n $ clarifications satisfying all constraints, with $ F $ being the maximum answer time over all clarifications.