Problem
Vers muss einen Bericht über den letzten Kampfflug vorbereiten. Sie hat bereits einen Text in ihrem Kopf komponiert, es bleibt nur übrig, ihn aufzuschreiben. Der Bericht besteht aus zwei Teilen: Der erste enthält n Wörter, die aus ai Buchstaben bestehen, der zweite enthält m Wörter, der zweite besteht aus bj Buchstaben. Die Kriya-Sprache enthält keine Satzzeichen. Vers sollte den Bericht auf eine karierte Papierrolle schreiben, die w Zellen breit ist. Da der Bericht aus zwei Teilen besteht, teilt er die Rolle durch einen vertikalen Strich in zwei Teile der ganzen Breite auf, dann schreibt er den ersten Teil auf der linken Seite und den zweiten Teil auf der rechten Seite.
Beide Teile des Berichts werden ähnlich geschrieben, jeder auf seinem eigenen Teil der Rolle. Ein Buchstabe eines Wortes nimmt genau eine Zelle ein. Das erste Wort wird in der ersten Zeile der Rolle geschrieben, beginnend mit der linken Zelle dieses Teils der Rolle. Jedes nächste Wort sollte, wenn möglich, in derselben Zeile wie das vorherige geschrieben werden und von genau einer leeren Zelle getrennt werden.
Andernfalls wird es in der nächsten Zeile geschrieben, beginnend mit der linken Zelle. Wenn die Breite eines Rollenteils kleiner ist als die Länge eines Wortes, das in diesem Teil geschrieben werden soll, ist es unmöglich, diesen Teil des Berichts in einen Rollenteil dieser Breite zu schreiben.
Es ist garantiert, dass eine vertikale Linie gezogen werden kann, so dass beide Teile des Berichts geschrieben werden können. Vers möchte eine vertikale Linie so zeichnen, dass die Länge der Rolle, die ausreicht, um einen Bericht zu schreiben, minimal ist. Hilf ihr, diese minimale Länge zu finden.
Eingabe:
- die erste Zeile enthält drei ganze Zahlen w, n und m — die Breite der Rolle, die Anzahl der Wörter im ersten und zweiten Teil des Berichts (\(1 <= w <= 10^9\); \(1 <= n, m <= 100.000\));
- Die folgende Zeile enthält n ganze Zahlen ai — die Länge des ersten Wortes des ersten Teils des Berichts \(1 <= a_i <= 10^9\);
- Die folgende Zeile enthält m Ganzzahlen bj — die Länge des j Wortes des zweiten Teils des Berichts \(1 <= b_j <= 10^9\).
Es ist garantiert, dass es möglich ist, eine Linie so zu zeichnen, dass beide Teile des Berichts geschrieben werden können.
Eingabe: Geben Sie in einer einzelnen Zeile eine ganze Zahl aus, die die Mindestrollenlänge ausreicht, um einen Bericht zu schreiben.
Beispiele
| № |
Eingabe |
Ausgabe |
| 1 |
15 6 6
2 2 2 3 2 2
3 3 5 2 4 3
|
3 |
Hinweis
Im Beispieltest kann die Rolle in zwei Teile geteilt werden, indem eine Linie zwischen der 7. und 8. Spalte der Zellen gezogen wird und dann zwei Wörter in jeder Zeile in beiden Teilen des Berichts geschrieben werden.