E. Две подпоследовательности
ограничение по времени на тест
2 seconds
ограничение по памяти на тест
256 megabytes
ввод
stdin
вывод
stdout

На уроке информатики Валерий изучал сжатие данных. Учитель рассказал новый метод, который мы сейчас вам опишем.

Пусть {a1, a2, ..., an} — данная последовательность строк, которую необходимо сжать. Здесь и далее будем считать, что все строки имеют одинаковую длину и состоят только из символов 0 и 1. Определим функцию сжатия:

  • f(пустая последовательность) = пустая строка
  • f(s) = s.
  • f(s1, s2) = наименьшая по длине строка, у которой один из префиксов равен s1, а один из суффиксов равен s2. Например, f(001, 011) = 0011, f(111, 011) = 111011.
  • f(a1, a2, ..., an) = f(f(a1, a2, an - 1), an). Например, f(000, 000, 111) = f(f(000, 000), 111) = f(000, 111) = 000111.

Перед Валерой стоит серьезная задача — разделить данную последовательность {a1, a2, ..., an} на две подпоследовательности {b1, b2, ..., bk} и {c1, c2, ..., cm}, m + k = n, так, чтобы величина S = |f(b1, b2, ..., bk)| + |f(c1, c2, ..., cm)| приняла минимально возможное значение. Здесь |p| обозначает длину строки p.

Обратите внимание, что запрещается менять относительный порядок строк в подпоследовательностях. Разрешается делать одну из подпоследовательностей пустой. Каждый элемент исходной последовательности должен принадлежать ровно одной из получившихся подпоследовательностей. Элементы подпоследовательностей b и c не обязательно должны идти подряд в исходной последовательности a, то есть они могут чередоваться (смотрите примеры 2 и 3).

Помогите Валере найти минимальное возможное значение S.

Входные данные

В первой строке входных данных содержится целое число n — количество строк (1 ≤ n ≤ 2·105). Далее в n строках даны элементы последовательности — строки длиной от 1 до 20 символов, состоящие только из символов 0 и 1. На i + 1 строке входных данных находится i-ый член последовательности. Элементы последовательности разделены исключительно символом перевода строки. Гарантируется, что все строки имеют одинаковую длину.

Выходные данные

Выведите единственное число — минимально возможное значение S.

Примеры
Входные данные
3
01
10
01
Выходные данные
4
Входные данные
4
000
111
110
001
Выходные данные
8
Входные данные
5
10101
01010
11111
01000
10010
Выходные данные
17
Примечание

Подробные ответы к тестам:

  • Оптимальный вариант: сделать одну из подпоследовательностей пустой, а вторую — равной всей данной последовательности. S = |f(01, 10, 01)| = |f(f(01, 10), 01)| = |f(010, 01)| = |0101| = 4.
  • Оптимальный вариант: b = {000, 001}, c = {111, 110}. S = |f(000, 001)| + |f(111, 110)| = |0001| + |1110| = 8.
  • Оптимальный вариант: b = {10101, 01010, 01000}, c = {11111, 10010}. S = |10101000| + |111110010| = 17.