Branded Bracelets
Limits: 2 sec., 256 MiB
Zenyk and Marichka want to present participants of Algorithmic Leo Camp (ALCamp) branded bracelets.
They have \(n\) strings \(s_i\). In order to produce one bracelet, they take several (possibly one) strings, concatenate them in arbitrary order and glue the last character to the first one. In this way they get a bracelet with a cyclic string.
Marichka and Zenyk can produce many bracelets.
Every string can be used in only one bracelet.
What is the maximum possible total number of occurences of the string
ALC in all bracelets?
Input
The first line contains an integer \(n\) — the number of strings.
The next \(n\) lines contain the strings \(s_i\).
Output
In the single print an integer – answer to the problem.
Constraints
\(1 \le n \le 10^5\),
the total length of all strings does not exceed \(10^5\).
Samples
| Input (stdin) | Output (stdout) |
|---|---|
| 3 LCBAL CEDAL COA | 3 |
Notes
It is optimal to produce one bracelet of the first and third strings
and the second bracelet of the second string in the sample. The first
bracelet is
LCBALCOA
and the second one is
CEDAL. It’s not the only
way to achieve the optimal answer.
| Element Type | Created | Who | Problem | Compiler | Result | Time (sec.) | Memory (MiB) | # | Actions |
|---|