Processor
Most modern processors are multi-core, allowing them to execute multiple instructions simultaneously. Paraltel has developed a new dual-core processor capable of executing 26 distinct instructions, represented by capital Latin letters. Each instruction takes exactly one clock cycle to execute.
A program for this processor is a sequence of instructions that must be executed in the order they appear; rearranging them is not permitted.
With two cores, the processor can run two programs at the same time, one on each core. However, due to its architecture, only identical instructions can be executed simultaneously on both cores.
When running two programs, a special control unit optimizes execution to finish both as quickly as possible. For instance, the programs "ABB" and "ABC" can be completed in 4 cycles: first, the "A" instructions from both programs run simultaneously, then the "B" instructions, followed by the "B" from the first program, and finally the "C" from the second. Similarly, the programs "CAB" and "BAB" take 4 cycles.
Recently, the company built a supercomputer with n processors to execute 2n programs. Each processor must run exactly two programs, one on each core.
Your task is to schedule the execution of these 2n programs on n processors to minimize the total completion time.
Input
The first line contains the number n (1 ≤ n ≤ 10) — the number of processors. The next 2n lines list the programs to be executed. Each program consists of 1 to 100 commands, each represented by a capital Latin letter.
Output
Output a single number — the minimum time required to execute all programs.