Problem
Vers deve preparare un rapporto sull'ultima sortita. Ha già composto il testo nella sua testa, non resta che scriverlo. Il report sarà composto da due parti: la prima conterrà n parole, ith delle quali è composta da ai< / codice> lettere, la seconda — m parole, la cui jesima consiste di bj lettere. La lingua Kriya non contiene segni di punteggiatura. Vers deve scrivere il rapporto su un rotolo di carta a quadretti, largo w celle. Poiché il rapporto è composto da due parti, dividerà il rotolo in due parti dell'intera larghezza con una linea verticale, dopodiché scriverà la prima parte sul lato sinistro e sulla destra — secondo.
Entrambe le parti del rapporto sono scritte allo stesso modo, ciascuna sulla propria parte del rotolo. Una lettera della parola occupa esattamente una cella. La prima parola è scritta nella prima riga del rotolo, partendo dalla cella più a sinistra di questa parte del rotolo. Ogni parola successiva, se possibile, dovrebbe essere scritta sulla stessa riga della precedente ed essere separata da essa esattamente da una cella vuota.
Altrimenti, è scritto nella riga successiva, partendo dalla cella più a sinistra. Se la larghezza di una parte del rotolo è inferiore alla lunghezza di qualche parola che dovrebbe essere scritta in questa parte, è impossibile scrivere questa parte del rapporto su una parte del rotolo di tale larghezza.
È garantito che si possa tracciare una barra verticale in modo da poter scrivere entrambe le parti del report. Vers vuole tracciare una linea verticale in modo che la lunghezza del rotolo, sufficiente per scrivere una relazione, sia minima. Aiutala a trovare quella lunghezza minima.
Inserimento:
- la prima riga contiene tre numeri interi w, n e m — larghezza rotolo, numero di parole nella prima e nella seconda parte del rapporto (\(1 <= w <= 10^9\); \(1 <= n, m <= 100 000\));
- la riga successiva fornisce n numeri interi ai — lunghezza della i-esima parola della prima parte del referto \(1 <= a_i <= 10^9\);
- la riga successiva fornisce m numeri interi bj — lunghezza della jesima parola della seconda parte del report \(1 <= b_j <= 10^9\).
È garantito che è possibile tracciare una linea in modo che entrambe le parti del rapporto possano essere scritte.
Input: in una singola riga stampa un singolo numero intero — la lunghezza minima del rotolo, sufficiente per scrivere una relazione.
Esempi
| # |
Input |
Uscita |
| 1 |
15 6 6
2 2 2 3 2 2
3 3 5 2 4 3
|
3 |
Nota
Nel test di esempio, il rotolo può essere diviso in due parti tracciando una linea tra la 7a e l'8a colonna di celle, e poi scrivendo due parole per riga in entrambe le parti del rapporto.