Processing math: 56%

Задача 4. Массивы-палиндромы

Входной файл:Стандартный вход   Ограничение времени:2 сек
Выходной файл:Стандартный выход   Ограничение памяти:512 Мб
Максимальный балл:100  

Условие

Кай работает в лаборатории изучения массивов, он экспериментирует с двумя массивами натуральных чисел: A=[a1,a2,,an] длины n и B=[b1,b2,,bm] длины m.

Эксперимент, который проводит Кай, устроен следующим образом. У каждого из массивов отбрасывается произвольный, возможно пустой, префикс, а также произвольный, возможно пустой, суффикс, таким образом, чтобы оставшиеся части массивов имели равную длину. Обозначим получившиеся массивы как A и B, а их длину как k. Затем Кай суммирует поэлементно получившиеся массивы, итоговый массив Кай обозначает как C=[c1,c2,,ck].

Пусть, например, n=5, A=[4,3,3,2,1], m=6, B=[4,1,5,1,3,2], от массива A отбрасывается первый и последний элемент, от массива B три первых. После этого массивы имеют вид A=[3,3,2], B=[1,3,2], результат их поэлементного суммирования C=[4,6,4].

Задача Кая заключается в том, чтобы получать такие C, которые являются массивами-палиндромами, то есть если числа на первой и последней позиции совпадают, числа на второй и предпоследней позиции совпадают, и так далее, для всех i числа на позициях i и ki+1 совпадают.

Помогите Каю понять, какой максимальный по длине массив-палиндром он может получить в результате эксперимента.

Формат входных данных

В первой строке ввода даны два целых числа n и m — количество элементов в первом и во втором массиве, соответственно (1).

Во второй строке ввода даны n целых чисел a_{i} — массив A (1 \leqslant a_i \leqslant 100).

В третьей строке ввода даны m целых чисел b_{j} — массив B (1 \leqslant b_j \leqslant 100).

Формат выходных данных

Выведите единственное целое число — максимальное k, что Кай в результате эксперимента может получить массив-палиндром длины k.

Ограничения

1 \leqslant n,\,m \leqslant 100\,000

1 \leqslant a_i \leqslant 100

1 \leqslant b_j \leqslant 100

Система оценки

Баллы за каждую подзадачу начисляются только в случае, если все тесты для этой подзадачи и необходимых подзадач успешно пройдены.

Подзадача Баллы Ограничения Необходимые подзадачи Информация о проверке
1 13 n,\,m \le 300 первая ошибка
2 33 все элементы массива B одинаковые первая ошибка
3 16 n \le 500, m \le 10^5 1 первая ошибка
4 38 1 — 3 первая ошибка

Примеры тестов

Стандартный вход Стандартный выход
1
5 6
4 3 3 2 1
4 1 5 1 3 2
3

0.145s 0.026s 13