Maximizing Adjacent Equal Pairs in Merged Binary Sequences

You are given n binary strings (each string consists only of the characters 0 and 1). You can perform the following operation any number of times:

Choose one of the strings, remove its first character, and append that character to the end of a new string S.

The relative order of the characters in each string must be preserved. In other words, if a string is initially s = s₁s₂…s_k, the characters must be removed in that order.

Your task is to determine a strategy to merge all characters from the n strings into S so that the number of adjacent indices i such that

[ S_i = S_{i+1} ]

is maximized.

Observation: If you take an entire string as a contiguous block rather than splitting it, you get a fixed number of internal equal‐adjacent pairs. For a string s of length L, let its internal bonus be defined as

[ B_{\text{internal}} = \sum_{i=2}^{L} [s_i = s_{i-1}], ]

and if the block ends with character c and the next block starts with the same character c, you receive an extra bonus of 1. Since the extraction order for each string is fixed, it is always optimal to remove an entire string consecutively. Therefore, the problem reduces to ordering the n blocks (each block being one of the given strings) to maximize the chain bonus defined by the transitions between consecutive blocks.

Formally, for each string s, define:

• start(s): the first character of s
• end(s): the last character of s
• B_internal(s): the number of indices i (2 ≤ i ≤ length(s)) for which s_i = s_i-1

If you order the strings as s⁽¹⁾, s⁽²⁾, …, s⁽ⁿ⁾, the total bonus is:

[ B = \sum_{j=1}^n B_{internal}(s^{(j)}) + \sum_{j=1}^{n-1} \mathbf{1}{ end(s^{(j)}) = start(s^{(j+1)}) }]

Your task is to compute the maximum achievable value of B.

inputFormat

The input begins with a single integer n (1 ≤ n ≤ 16), indicating the number of binary strings.

Each of the next n lines contains a non‐empty binary string consisting only of characters 0 and 1.

outputFormat

Output a single integer: the maximum number of adjacent equal pairs in the merged string S when an optimal merging strategy is used.

sample

3
0
00
1

2