Preventing Farm Identity Theft

Farmer John has N cows, each having a farm identification number in the form of a binary string (composed only of characters 0 and 1). Bessie, the eldest cow, memorizes all these IDs and often asks cows for their ID. When a cow is asked for her ID, she begins reciting her binary string but may get confused and stop reciting before finishing.

After hearing the recited string (which may be a prefix of the cow's full ID), Bessie checks the farm records. If the reported string does not match any cow’s full ID, she merely shrugs. However, if it exactly equals the full ID of some other cow, then she concludes that an identity theft has occurred and locks down the entire farm. Note that this danger may occur even if the cow finishes reciting her correct, full ID.

In order to prevent such a lock‐down, Farmer John is willing to add extra binary digits (bits) to (i.e. append to) some cows’ IDs. It takes one second to append one bit to a cow’s current ID. Determine the minimum total time (in seconds) required so that after appending bits, the final set of IDs will be safe, i.e. no final ID is a prefix of another. (Formally, if a cow’s original ID is s and she is appended an extra string x (possibly empty) so that her final ID is s x, then the final set must satisfy that for any two different cows, the final ID of one is not a prefix of the final ID of the other.)

One may prove that this is equivalent to ensuring that for any two cows whose original IDs are comparable (one is a prefix of the other, or they are exactly the same), both are modified so that their final IDs have equal length and are different. In particular, if a cow’s full original ID is s and there is another cow whose full original ID has s as a prefix, then the cow with s must have at least one extra bit appended (choosing the extra bits so that her final ID is not equal to the other cow’s full (or final) ID).

More precisely, suppose a cow has an original ID s and there exists some conflicting cow (either because there is a duplicate s or some other cow’s ID has s as a prefix). Let p be the shortest prefix of the cow’s ID that appears in the input and is conflicting (a conflicting ID is one that either appears at least twice or is a prefix of another cow’s ID). Then, if there are k cows having p as their chosen group indicator, they all must have their final IDs of the same length, say L, where

The extra time for each cow in that group is L - |s|, and the total extra time is the sum over all cows. For cows that are not involved in any conflict, no extra bit is needed.

inputFormat

The first line contains a single integer N (1 ≤ N ≤ 10⁵), the number of cows.

The following N lines each contain a nonempty binary string representing a cow's farm ID. The binary string consists only of characters 0 and 1.

outputFormat

Output a single integer: the minimum total number of seconds required (i.e. the minimum total number of extra appended bits) so that no final ID is a prefix of another.

sample

2
101
1011

1