팰린드롬 배열
시간 제한2초메모리 제한512 MB
두 배열에서 같은 길이의 연속 구간을 골라 원소별 합이 회문이 되도록 할 때, 가능한 가장 긴 길이를 구합니다.
문제
카이는 배열 실험실에서 자연수로 이루어진 두 배열을 가지고 실험한다. 길이가 인 배열 과 길이가 인 배열 이다. 실험은 다음과 같이 진행된다. 각 배열에서 임의의 접두사와 임의의 접미사를 잘라낸다. 둘 다 비어 있어도 된다. 남은 두 부분의 길이는 같아야 한다. 남은 배열을 , 라 하고, 공통 길이를 라 한다. 그런 다음 카이는 두 배열을 원소별로 더해 배열 를 만든다. 예를 들어 , , , 라고 하자. 카이는 에서 첫 원소와 마지막 원소를 버리고, 에서 처음 세 원소를 버린다. 그러면 , 이고, 원소별 합은 이다. 카이는 가 팰린드롬 배열이기를 원한다. 즉 모든 에 대해 위치 와 위치 의 원소가 같아야 한다. 카이가 실험으로 얻을 수 있는 팰린드롬 배열의 최대 길이를 구하라.
입력
첫 줄에 두 정수 과 이 주어진다. 각각 첫 번째 배열과 두 번째 배열의 원소 개수다 (). 둘째 줄에는 배열 의 정수 개 가 주어진다 (). 셋째 줄에는 배열 의 정수 개 가 주어진다 ().
출력
카이가 실험으로 길이 의 팰린드롬 배열을 얻을 수 있는 최대 를 정수 하나로 출력하라.