시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
2 초 128 MB 15 4 4 26.667%

문제

여러 개의 정원과 여러 개의 이랑(일렬로 나무나 곡식을 심는 길쭉한 길)을 소유한 한 농부가 있다. 정원의 경계는 사이프러스 나무로 둘러싸여 있으며, 각 이랑에도 사이프러스 나무가 심어져 있다. 또한 정원과 이랑 모두, 두 사이프러스 나무 사이에는 올리브 나무가 한 그루 심어져 있다. 이런 식으로 농부의 모든 사이프러스 나무는 정원을 둘러싸거나 이랑을 따라 심어져 있으며, 사이프러스 나무 두 그루 사이에는 반드시 올리브 나무가 한 그루 끼여 있다.

그러던 어느 날, 농부는 심한 병에 걸려 임종을 앞두게 되었다. 숨을 거두기 며칠 전, 그는 맏아들에게 이렇게 말했다. "내 정원과 이랑에 심어진 사이프러스 나무들을 아무 거나 Q 그루 골라라. 그러면 그 나무들과, 두 나무 사이에 심겨져 있는 올리브 나무까지 모두 네게 주겠다."

아버지의 유언에 따라 아들은 정원 경계나 이랑에서 연속하는 구간을 하나 이상 선택하여 사이프러스 나무를 최대 Q 그루까지 얻을 수 있고, 그 사이에 있는 올리브 나무들도 얻을 수 있다. 아들은 올리브를 매우 좋아하기 때문에 올리브 나무를 가장 많이 얻을 수 있는 구간을 선택하고 싶어 한다.

농부에게 정원과 이랑이 세 개씩 있고, 사이프러스 나무가 각 곳에 위의 그림과 같이 있다고 가정하자. (사이프러스 나무 사이에 있는 올리브 나무는 편의상 표기하지 않았다) 그리고 Q=17그루의 사이프러스 나무를 물려받을 수 있다고 하자. 그렇다면 아들은 정원 1과 2에 있는 사이프러스 나무만을 모두 선택하면 된다. 정원은 이랑과는 달리 고리를 이루고 있기 때문에, 그 안에 있는 17그루의 올리브 나무를 모두 물려받을 수 있기 때문이다.

밭과 이랑에 있는 나무 수와 물려받을 수 있는 나무의 수를 입력으로 받아, 아들이 물려받을 수 있는 올리브 나무의 최대 수를 구하는 프로그램을 작성하시오.

입력

첫째 줄에는 아들이 물려받을 수 있는 나무의 그루 수 Q와, 정원의 수 M, 그리고 이랑의 수 K가 들어있다. 둘째 줄에는 각 정원에 있는 사이프러스 나무의 수를 나타내는 정수가 M개 있으며, 다음 줄에는 각 이랑에 있는 사이프러스 나무의 수를 나타내는 정수가 K개 있다.

0≤ Q ≤15만, 0≤ M, K ≤2000이고, 한 정원이나 이랑에 있는 나무의 수는 2 이상 150 이하이다. 모든 정원과 이랑에 있는 나무들의 총합은 반드시 Q보다 같거나 크다.

출력

아들이 덤으로 받을 수 있는 올리브 나무의 최대 그루 수를 출력한다.

예제 입력

17 3 3
13 4 8
4 8 6

예제 출력

17

힌트