Problem
Vers は、最後の出撃に関するレポートを作成する必要があります。彼女はすでに頭の中でテキストを構成しており、それを書き留めるだけです。レポートは 2 つの部分で構成されます。最初の部分には n 語が含まれ、 i 番目は ai< で構成されます。 / code> 文字、2 番目の — m 個の単語で、その j 番目は bj 文字で構成されています。クリヤ語には句読点がありません。 Vers は、w セル幅の市松模様のロール紙にレポートを書かなければなりません。レポートは 2 つの部分で構成されているため、ロール全体を縦線で 2 つの部分に分割し、最初の部分を左側に、右側に書き込みます。秒。
レポートの両方の部分は同じ方法で書かれており、それぞれがロールの独自の部分に書かれています。単語の 1 文字がちょうど 1 つのセルを占めます。最初の単語は、ロールのこの部分の左端のセルから開始して、ロールの最初の行に書き込まれます。次の各単語は、可能であれば、前の単語と同じ行に記述し、空のセル 1 つだけで区切る必要があります。
それ以外の場合は、左端のセルから次の行に書き込まれます。ロールの一部の幅が、この部分に書かれるべき単語の長さより短い場合、そのような幅のロールの一部にレポートのこの部分を書くことは不可能です.
レポートの両方の部分を記述できるように、垂直バーを描画できることが保証されています。 Vers は、レポートを書くのに十分なロールの長さが最小限になるように、垂直線を引きたいと考えています。最小の長さを見つけるのを手伝ってください。
入力:
- 最初の行には、3 つの整数 w、n、および m が含まれます —ロール幅、レポートの最初と 2 番目の部分の単語数 (\(1 <= w <= 10^9\); \(1 <= n, m <= 100 000\));
- 次の行は n 個の整数 ai を与えます —レポートの最初の部分の i 番目の単語の長さ \(1 <= a_i <= 10^9\);
- 次の行は m 個の整数 bj を与えます—レポートの 2 番目の部分の j 番目の単語の長さ \(1 <= b_j <= 10^9\).
レポートの両方の部分を書くことができるように線を引くことができることが保証されています.
入力: 1 行に 1 つの整数を出力します —レポートを書くのに十分なロールの最小の長さ。
例
<頭>
| # |
入力 |
出力 |
<本体>
| 1 |
15 6 6
2 2 2 3 2 2
3 3 5 2 4 3
|
3 |
注意
サンプル テストでは、ロールを 7 列目と 8 列目のセルの間に線を引き、レポートの両方の部分に 1 行に 2 語ずつ書くことで、ロールを 2 つの部分に分けることができます。