Задача
Верс нужно подготовить рапорт о последнем боевом вылете. Она уже сочинила в голове текст, осталось лишь его записать. Рапорт будет состоять из двух частей: первая будет содержать n слов, i-е из которых состоит из ai букв, вторая — m слов, j-е из которых состоит из bj букв. Язык Крии не содержит никаких знаков препинания. Верс должна записать рапорт на клетчатом рулоне бумаги, шириной w клеток. Так как рапорт состоит из двух частей, она разделит вертикальной чертой рулон на две части целой ширины, после чего в левой части напишет первую часть, а в правой — вторую.
Обе части рапорта записываются аналогично, каждая на своей части рулона. Одна буква слова занимает ровно одну клетку. Первое слово записывается в первой строке рулона, начиная с самой левой клетки этой части рулона. Каждое следующее слово, если это возможно, должно быть записано в той же строке, что и предыдущее, и быть отделено от него ровно одной пустой клеткой.
Иначе, оно пишется в следующей строке, начиная с самой левой клетки. Если ширина части рулона меньше, чем длина какого-то слова, которое должно быть написано в этой части, написать эту часть рапорта на части рулона такой ширины невозможно.
Гарантируется, что можно провести вертикальную черту так, что обе части рапорта возможно написать. Верс хочет провести вертикальную черту так, чтобы длина рулона, которой хватит, чтобы написать рапорт, была минимальна. Помогите ей найти эту минимальную длину.
Входные данные:
- в первой строке даны три целых числа w, n и m — ширина рулона, количество слов в первой и второй части рапорта (\(1 <= w <= 10^9\); \(1 <= n, m <= 100 000\));
- в следующей строке дано n целых чисел ai — длина i-го слова первой части рапорта \(1 <= a_i <= 10^9\);
- в следующей строке дано m целых чисел bj — длина j-го слова второй части рапорта \(1 <= b_j <= 10^9\).
Гарантируется, что возможно провести черту так, что обе части рапорта возможно написать.
Входные данные: в единственной строке выведите одно целое число — минимальную длину рулона, которой достаточно, чтобы написать рапорт.
Примеры
| № |
Входные данные |
Выходные данные |
| 1 |
15 6 6
2 2 2 3 2 2
3 3 5 2 4 3
|
3 |
Примечание
В тесте из примера рулон можно разделить на две части, проведя черту между 7 и 8 столбцом клеток, а затем записать по два слова в каждой строке в обеих частях рапорта.