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