Процессор
Як відомо, більшість процесорів, які зараз випускаються, є багатоядерними, тобто підтримують виконання декількох інструкцій одночасно. Компанія Paraltel розробила новий тип двоядерного процесора, який дозволяє вмконувати 26 різних инструкций, які позначаються великими латинськими літерами. Виконання кожної такої інструкції вимагає рівно одного такту роботи процесора.
Програма для цього процесора являє собою послідовність інструкцій. Інструкції програми повинні бути виконані у тому порядку, у якому вони йдуть у програмі, міняти місцями інструкції не дозволяється.
Завдяки наявності двох ядер, процесор може одночасно виконувати дві програми — по одній на кожному ядрі. Проте із-за особливостей архітектури одночасно на двох ядрах одного процесора можуть виконуватись лише однакові інструкції.
При виконанні двох програм на процесорі спеціальний керуючий пристрій оптимізує виконання так, щоб завершити виконання обох програм якомога раніше. Наприклад, програми "ABB" та "ABC" можна виконати на процесорі за 4 такти: спочатку одночасно виконуютбся команди "A" обох програм на різних ядрах, потім одночасно команди "B", потім команда "B" з першої програми і, нарешті, "C" з другої. Аналогічно, програми "CAB" та "BAB" виконуються за 4 такти.
Нещодавно спеціалісти компанії зібрали з n процесорів суперкомп'ютер, на якому потрібно виконати 2n програм. Організація обчислень така, що кожен процесор повинен выконати рівно по дві програми з цього набору, по одній на кожному ядрі.
Вам необхідно спланувати виконання 2n програм на n процесорах так, щоб час завершення виконання усіх програм був мінімальним.
Вхідні дані
У першому рядку задано число n (1 ≤ n ≤ 10) — кількість процесорів. Далі, у 2n рядках задано програми, які необхідно виконати. Кожна програма містить від 1 до 100 команд. Кожна команда подається великою латинською літерою.
Вихідні дані
Виведіть єдине число — мінімальний час, за який можна виконати усі програми.