Арифметика и числовые алгоритмы

Летние учебно-тренировочные сборы кандидатов в сборную России по информатике, Малоярославец, 27 июня 2006 года

Задача A. Дырявая лента

Имя входного файла	holytape.in
Имя выходного файла	holytape.out
Ограничение по времени	10 секунд
Ограничение по памяти	64 мегабайта

За сверхполезные исследования в области просвета ключей, содержащих прямоугольные дырки, руководство НИИ Исследований Данных Строк присудило Васе специальную премию. Вдохновленный полученными результатами и поддержкой руководства, Вася решил пойти дальше и попробовать на просвет другие объекты. И вот, он держит в руках две древние телетайпные ленты!

Каждая телетайпная лента – это бесконечная в обе стороны лента бумаги. Начиная с некоторого места, на ленте дырочками закодировано сообщение. Сообщение состоит из K позиций, представленных на ленте ячейкой 1 × 1 сантиметр каждая. Ширина ленты составяет 3 сантиметра.

В каждой из позиций ленты, отвечающей за кодирование сообщения, либо есть дырочка (тогда соответствующий бит сообщения равен единице), либо нет (в этом случае бит равен нулю). Если в соседних позициях есть дырочки, то они сливаются.

Например, если сообщение выглядело как 01110010111011, то лента будет выглядеть таким образом:

Вася хочет научиться накладывать одну ленту на другую таким образом, чтобы на просвет образовывалось как можно больше дырочек. Кроме этого, требуется, чтобы приведенную ленту можно было вставить в декодирующее устройство, т.е. длина каждого просвета и расстояние между любыми просветами выражались бы целым числом сантиметров, а края лент были совмещены. Поворачивать и переворачивать ленты запрещается. Напишите про грамму, которая по заданным сообщениям определяла бы, какое максимальное количество дырочек можно получить.

Формат входного файла

Входной файл состоит из двух строк: в первой строке задается сообщение, записанное на первой ленте, на второй – записанное на второй. Сообщения непусты, и состоят не более, чем из 130 000 битов.

Формат выходного файла

В выходной файл выведите максимально возможное количество дырочек.

Пример

holytape.in	holytape.out
01110010111011 1001001001	4
11111111111000000000110000000 00001100000000000000001111111	2

В первом примере можно, например, сдвинуть вторую ленту вправо на 3 сантиметра относительно первой. Во втором примере одним из возможных оптимальных сдвигов является сдвиг влево на 2 см.