Задача . E. Две подпоследовательности

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

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

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

Перед Валерой стоит серьезная задача — разделить данную последовательность {a₁, a₂, ..., a_n} на две подпоследовательности {b₁, b₂, ..., b_k} и {c₁, c₂, ..., c_m}, m + k = n, так, чтобы величина S = |f(b₁, b₂, ..., b_k)| + |f(c₁, c₂, ..., c_m)| приняла минимально возможное значение. Здесь |p| обозначает длину строки p.

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

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