보고서

면접 대비

시간 제한2초메모리 제한1024 MB

요약

두 단어 목록을 w 칸 너비의 두루마리 왼쪽과 오른쪽에 나눠 쓸 때, 줄을 바꾸며 필요한 줄 수가 가장 적은 나눔을 찾아 그 줄 수를 구합니다.

난이도: 보통10점 중 5점
유형: 이분 탐색, 그리디, 시뮬레이션
정답자: 아직 제출이 없습니다

문제

베르스는 마지막 전투 비행에 대한 보고서를 써야 한다. 머릿속으로 글은 이미 구상해 두었고, 이제 적기만 하면 된다. 보고서는 두 부분으로 이루어진다. 첫 부분은 $n$ 개의 단어로 이루어지고, $i$ 번째 단어는 $a_i$ 개의 글자로 이루어진다. 둘째 부분은 $m$ 개의 단어로 이루어지고, $j$ 번째 단어는 $b_j$ 개의 글자로 이루어진다. 크리아 언어에는 문장 부호가 없다. 베르스는 보고서를 폭이 $w$ 칸인 모눈종이 두루마리에 적어야 한다. 보고서가 두 부분이므로 세로선을 그어 두루마리를 정수 폭의 두 부분으로 나누고, 왼쪽에는 첫 부분을, 오른쪽에는 둘째 부분을 적는다.

두 부분은 같은 방식으로, 각자의 부분에 적는다. 글자 하나는 정확히 한 칸을 차지한다. 첫 단어는 그 부분의 가장 왼쪽 칸에서 시작해 첫 줄에 적는다. 다음 단어는 들어갈 수 있으면 바로 앞 단어와 같은 줄에, 정확히 한 빈 칸을 사이에 두고 적는다. 들어갈 수 없으면 다음 줄의 가장 왼쪽 칸에서 시작한다. 어떤 부분에 적어야 할 단어의 길이가 그 부분의 폭보다 크면, 그 폭으로는 그 부분을 적을 수 없다.

두 부분을 모두 적을 수 있도록 세로선을 그을 수 있다고 보장된다. 베르스는 보고서를 적는 데 필요한 두루마리 길이가 최소가 되도록 선을 긋고 싶어 한다. 이 최소 길이를 구하라.

입력

첫 줄에 세 정수 $w$ , $n$ , $m$ 이 주어진다. $w$ 는 두루마리의 폭( $1 \le w \le 10^9$ )이고, $n$ 과 $m$ 은 첫 부분과 둘째 부분의 단어 수( $1 \le n, m \le 100\,000$ )이다.

다음 줄에 $n$ 개의 정수 $a_i$ 가 주어진다. $a_i$ 는 첫 부분의 $i$ 번째 단어의 길이이다( $1 \le a_i \le 10^9$ ).

그다음 줄에 $m$ 개의 정수 $b_j$ 가 주어진다. $b_j$ 는 둘째 부분의 $j$ 번째 단어의 길이이다( $1 \le b_j \le 10^9$ ).

두 부분을 모두 적을 수 있도록 세로선을 그을 수 있다고 보장된다.

출력

보고서를 적기에 충분한 두루마리의 최소 길이를 정수 하나로 출력한다.

힌트

예제에서는 두루마리를 7번째 칸과 8번째 칸 사이에서 나누고, 보고서의 두 부분 모두 각 줄에 단어를 두 개씩 적는다.

예제1

예제 1
입력
```
15 6 6
2 2 2 3 2 2
3 3 5 2 4 3
```
예상 출력
```
3
```