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

Входной файл:Стандартный вход   Ограничение времени: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 и k − i + 1 совпадают.

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

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

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

Во второй строке ввода даны n целых чисел ai — массив A (1 ⩽ ai ⩽ 100).

В третьей строке ввода даны m целых чисел bj — массив B (1 ⩽ bj ⩽ 100).

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

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

Ограничения

1 ⩽ n, m ⩽ 100 000

1 ⩽ ai ⩽ 100

1 ⩽ bj ⩽ 100

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

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

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

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

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

0.363s 0.206s 15