Report

Interview

Time limit2sMemory limit1024 MB

Summary

Split two word lists by a vertical line on a w-wide roll so the greedy line-wrapping needs the fewest rows, then print that row count.

Level: Medium5 of 10
Topics: Binary search, Greedy, Simulation
Solved: No attempts yet

Statement

Vers needs to prepare a report on her last combat sortie. She has already composed the text in her head, and only has to write it down. The report has two parts: the first contains $n$ words, the $i$ -th of which has $a_i$ letters, and the second contains $m$ words, the $j$ -th of which has $b_j$ letters. The Kria language has no punctuation marks. Vers must write the report on a squared paper roll that is $w$ cells wide. Since the report has two parts, she draws a vertical line across the roll, splitting it into two parts of whole width, then writes the first part on the left and the second part on the right.

Both parts are written in the same way, each on its own part of the roll. One letter takes exactly one cell. The first word is written on the first line of the roll, starting from the leftmost cell of that part. Each following word is written on the same line as the previous word if it fits, separated from it by exactly one empty cell. Otherwise it goes on the next line, starting from the leftmost cell. If the width of a part is less than the length of some word that must be written in it, writing that part on a roll of that width is impossible.

It is guaranteed that a vertical line can be drawn so that both parts can be written. Vers wants to draw the line so that the length of the roll needed to write the report is minimal. Find this minimal length.

Input

The first line contains three integers $w$ , $n$ , and $m$ , where $w$ is the width of the roll ( $1 \le w \le 10^9$ ) and $n$ , $m$ are the numbers of words in the first and second parts ( $1 \le n, m \le 100\,000$ ).

The next line contains $n$ integers $a_i$ , the length of the $i$ -th word of the first part ( $1 \le a_i \le 10^9$ ).

The next line contains $m$ integers $b_j$ , the length of the $j$ -th word of the second part ( $1 \le b_j \le 10^9$ ).

It is guaranteed that a vertical line can be drawn so that both parts can be written.

Output

Print one integer, the minimal length of the roll that is enough to write the report.

Hint

In the sample test, the roll is split between the 7th and 8th columns of cells, and then two words are written on each line in both parts of the report.

Examples1

Example 1
Input
```
15 6 6
2 2 2 3 2 2
3 3 5 2 4 3
```
Expected output
```
3
```