농부
시간 제한2초메모리 제한128 MB
예산 Q개의 삼나무를 원형 정원과 직선 이랑에서 골라 얻는 올리브 나무 수를 최대화하는데, 정원 전체를 선택하면 n개를 얻지만 부분 선택이나 이랑 선택은 선택한 개수보다 하나 적은 올리브 나무를 얻는 문제입니다.
문제
농부는 여러 개의 정원과 여러 개의 이랑을 가지고 있다. 정원은 닫힌 고리 모양이고, 이랑은 양 끝이 이어지지 않은 일직선이다. 정원의 둘레와 이랑에는 사이프러스 나무가 심어져 있으며, 같은 정원 또는 같은 이랑에서 서로 이웃한 두 사이프러스 나무 사이에는 올리브 나무가 정확히 한 그루 있다.
아들은 정원의 둘레나 이랑 위에서 연속한 구간을 하나 이상 고를 수 있다. 고른 구간들에 포함된 사이프러스 나무의 총수가 Q그루 이하가 되면, 아들은 그 사이프러스 나무들과 각 구간 안에서 연속한 두 사이프러스 나무 사이에 놓인 올리브 나무를 받는다.
정원은 고리이므로, 어떤 정원에 있는 사이프러스 나무를 모두 고르면 마지막 나무와 첫 번째 나무 사이의 올리브 나무까지 받는다. 따라서 사이프러스 나무가 n그루인 정원 전체를 고르면 올리브 나무 n그루를 받을 수 있다. 반대로 이랑이나 정원의 일부 구간에서 사이프러스 나무 x그루를 연속해서 고르면 받을 수 있는 올리브 나무는 x-1그루이다.
정원과 이랑에 있는 사이프러스 나무의 수가 주어질 때, 아들이 받을 수 있는 올리브 나무의 최대 그루 수를 구하시오.
입력
첫째 줄에 아들이 고를 수 있는 사이프러스 나무의 최대 수 Q, 정원의 수 M, 이랑의 수 K가 주어진다. 둘째 줄에는 각 정원에 있는 사이프러스 나무의 수를 나타내는 정수 M개가 주어진다. 셋째 줄에는 각 이랑에 있는 사이프러스 나무의 수를 나타내는 정수 K개가 주어진다.
0 ≤ Q ≤ 150,000, 0 ≤ M, K ≤ 2,000이다. 각 정원이나 이랑에 있는 사이프러스 나무의 수는 2 이상 150 이하이다. 모든 정원과 이랑에 있는 사이프러스 나무 수의 합은 Q 이상이다.
출력
아들이 받을 수 있는 올리브 나무의 최대 그루 수를 출력한다.