Assembly of chains from fragments with maximum length

Kotlin Hard functions

Task «Assembly of chains from fragments with maximum length»

Given N strings consisting of lowercase Latin letters (each string length from 1 to 100). It is necessary to write a function that takes a list of strings and returns the maximum length of a chain that can be formed by concatenating strings sequentially so that the last character of the current string matches the first character of the next string. Each string can be used at most once. If it is impossible to form a chain, return 0.

Input Format

First line — integer N (1 ≤ N ≤ 20). Then N strings, one per line.

Output Format

Integer — the maximum length of the chain (the sum of the lengths of all strings in the chain).

Examples

Example 1

INPUT

10
20

OUTPUT

0

Example 2

INPUT

15
15

OUTPUT

0

main.kt