Problem H
Water Sort

Water Sort

In a water sort puzzle, a number of virtual vials is filled with $4$ layers of colored water that, contrary to the laws of Brownian motion, stay separated. There are also two empty vials that can hold up to $4$ layers. The goal of the puzzle is to sort the colored water so that each vial is either empty or contains water of only one color. Water may be poured between vials, subject to the following rules:

• Water of only one color may be poured at a time

• Water may be poured only into empty vials or into vials whose top layer is of the same color as the water being poured

• Vials may hold at most 4 layers, i.e., they cannot overflow

• You must always pour as much volume of a color as will fit into the target vial

Note that with these rules, the overall volume of water of each color stays the same after each operation.

Compute the minimum amount of water that must be poured until all vials are either empty or contain $4$ layers of water of the same color.

Input

The input consists of a single test case. The first contains an integer $n$ ($1 \le n \le 16$) denoting the number of full vials initially. This is followed by $4$ lines, each containing $n$ space separated lower case English letters. The letters are chosen consecutively, starting with a, then b, and so on. Each letter denotes a color, and there will be exactly $4$ occurrences of each letter.

Output

Output the minimum amount of water, counted in units of one quarter of a vial, that must be poured so that all the water is sorted. It does not matter which two vials remain empty when all vials are sorted. It is guaranteed that all puzzles are solvable.

Sample Input

In Sample Input 1, there are two vials: abba and baab. The following sequence of pours is one that solves this puzzle. Each pouring operation moves $1$, $1$, $2$, $2$, $1$, and $1$ quarts of water for a total of $8$.

a b _ _      _ b _ _      _ _ _ _      _ _ _ _      _ _ _ _      _ _ a _      _ b a _
b a _ _      b a _ _      b a _ _      b _ a _      _ b a _      _ b a _      _ b a _
b a _ _ =1=> b a _ _ =1=> b a _ _ =2=> b _ a _ =2=> _ b a _ =1=> _ b a _ =1=> _ b a _
a b _ _      a b a _      a b a b      a b a b      a b a b      _ b a b      _ b a _

2
a b
b a
b a
a b

8

9
a b c d e f d g a
e g f c h g a h i
f a i c h c h g d
b d b e i b f i e

35