Problem
Vers needs to prepare a report on the last sortie. She has already composed the text in her head, it remains only to write it down. The report will consist of two parts: the first will contain n words, ith of which consists of ai letters, the second — m words, the jth of which consists of bj letters. The Kriya language does not contain any punctuation marks. Vers must write the report on a checkered roll of paper, w cells wide. Since the report consists of two parts, she will divide the roll into two parts of the whole width with a vertical line, after which she will write the first part on the left side, and on the right — second.
Both parts of the report are written in the same way, each on its own part of the roll. One letter of the word occupies exactly one cell. The first word is written in the first line of the roll, starting from the leftmost cell of this part of the roll. Each next word, if possible, should be written on the same line as the previous one and be separated from it by exactly one empty cell.
Otherwise, it is written on the next line, starting from the leftmost cell. If the width of a part of the roll is less than the length of some word that should be written in this part, it is impossible to write this part of the report on a part of the roll of such a width.
It is guaranteed that a vertical bar can be drawn so that both parts of the report can be written. Vers wants to draw a vertical line so that the length of the roll, which is enough to write a report, is minimal. Help her find that minimum length.
Input:
- the first line contains three integers w, n and m — roll width, number of words in the first and second parts of the report (\(1 <= w <= 10^9\); \(1 <= n, m <= 100 000\));
- the next line gives n integers ai — length of the i-th word of the first part of the report \(1 <= a_i <= 10^9\);
- the next line gives m integers bj — length of the jth word of the second part of the report \(1 <= b_j <= 10^9\).
It is guaranteed that it is possible to draw a line so that both parts of the report can be written.
Input: in a single line print a single integer — the minimum length of the roll, which is enough to write a report.
Examples
| # |
Input |
Output |
| 1 |
15 6 6
2 2 2 3 2 2
3 3 5 2 4 3
|
3 |
Note
In the sample test, the roll can be divided into two parts by drawing a line between the 7th and 8th column of cells, and then writing two words per line in both parts of the report.