Maximizing Adjacent Identical Pairs in Appended Binary Strings

You are given n binary strings (each consisting of characters '0' and '1'). You can perform the following operation on any non‐empty string any number of times (note that each string can be reused):

Select one of the strings, remove its first character, and then append the remaining string to the end of another (initially empty) string S.

After a sequence of such operations (until all strings become empty), the string S becomes the concatenation of all the appended pieces. Your task is to choose the order in which you perform these removals in order to maximize the total number of adjacent pairs in S that consist of the same character. In other words, for each index i (1 ≤ i < |S|) you earn 1 point if S[i] == S[i+1] (using 1-indexing).

Important note: Even though the internal contribution (i.e. identical pairs inside each appended string) is fixed regardless of the order, you can increase the overall score by optimally interleaving the appended strings so as to maximize the number of pairs across boundaries of consecutive appended pieces. More formally:

• For a string s of length L, if you repeatedly remove the first character you will obtain a sequence of appended pieces:

For the first removal, the appended piece is s[2..L], for the second removal (applied on the remaining string) the appended piece is s[3..L], and so on. (Here, we use 1-indexing; if a removal produces an empty string, it does not affect S.)

Each such piece has an internal score equal to the number of indices within the piece where two consecutive characters are equal. This internal score is fixed. However, when concatenating two pieces A and B, you get an extra score of 1 if the last character of A equals the first character of B. The challenge is to choose the interleaving order of all removal operations (subject to the constraint that removals from the same string must remain in order) so as to maximize the sum of these extra boundary scores. The final answer is the sum of the fixed internal scores plus the extra boundary scores.

Compute and print the maximum possible score.

inputFormat

The input begins with a single integer n (1 ≤ n ≤ 10) – the number of binary strings. Then follow n lines, each containing a binary string. The length of each string is between 1 and 10 (inclusive).

outputFormat

Output a single integer representing the maximum possible score you can achieve by optimally choosing the order of removal operations.

sample

2
1010
111

4