Most modern processors are multi-core, allowing them to execute multiple instructions simultaneously. Paraltel has developed a new dual-core processor capable of executing 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 "" and "" can be completed in cycles: first, the "" instructions from both programs run simultaneously, then the "" instructions, followed by the "" from the first program, and finally the "" from the second. Similarly, the programs "" and "" take cycles.
Recently, the company built a supercomputer with processors to execute programs. Each processor must run exactly two programs, one on each core.
Your task is to schedule the execution of these programs on processors to minimize the total completion time.
The first line contains the number (1 \leq n \leq 10) — the number of processors. The next lines list the programs to be executed. Each program consists of to commands, each represented by a capital Latin letter.
Output a single number — the minimum time required to execute all programs.
Пример 1