Processor

Most processors manufactured today are multi-core, meaning they can execute several instructions at once. The company Paraltel has developed a new type of dual-core processor that can execute 26 different instructions, denoted by uppercase Latin letters. Executing each such instruction takes exactly one clock cycle of the processor.

A program for this processor is a sequence of instructions. The instructions of a program must be executed in the order they appear in the program; swapping instructions is not allowed.

Thanks to having two cores, the processor can execute two programs at the same time, one on each core. However, because of the architecture, two cores of the same processor can execute only identical instructions at the same time.

When running two programs on the processor, a special control unit optimizes execution so that both programs finish as early as possible. For example, the programs "ABB" and "ABC" can be executed on the processor in 4 cycles: first the "A" instructions of both programs are executed simultaneously on different cores, then the "B" instructions simultaneously, then the "B" of the first program, and finally the "C" of the second. Similarly, the programs "CAB" and "BAB" are executed in 4 cycles.

Recently the company's engineers assembled a supercomputer from n processors, on which 2n programs must be executed. The computation is organized so that each processor must execute exactly two programs from this set, one on each core.

You need to schedule the execution of the 2n programs on the n processors so that the time at which all programs finish is minimized.

The first line contains the number n (1 ≤ n ≤ 10), the number of processors. The next 2n lines contain the programs that must be executed. Each program contains from 1 to 100 commands. Each command is given by an uppercase Latin letter.

Print a single number, the minimum time in which all programs can be executed.