Problem
Vers necesita preparar un informe sobre la última salida. Ya ha compuesto el texto en su cabeza, solo queda escribirlo. El informe constará de dos partes: la primera contendrá n palabras, ith de las cuales constará de ai< / código> letras, el segundo & mdash; m palabras, la jésima de las cuales consta de bj letras. El idioma Kriya no contiene ningún signo de puntuación. Vers debe escribir el informe en un rollo de papel cuadriculado, de w celdas de ancho. Como el informe consta de dos partes, dividirá el rollo en dos partes de todo el ancho con una línea vertical, después de lo cual escribirá la primera parte en el lado izquierdo y en el lado derecho; segundo.
Ambas partes del informe están escritas de la misma manera, cada una en su propia parte del rollo. Una letra de la palabra ocupa exactamente una celda. La primera palabra se escribe en la primera línea del rollo, comenzando desde la celda más a la izquierda de esta parte del rollo. Cada palabra siguiente, si es posible, debe escribirse en la misma línea que la anterior y estar separada de ella exactamente por una celda vacía.
De lo contrario, se escribe en la siguiente línea, comenzando desde la celda más a la izquierda. Si el ancho de una parte del rollo es menor que la longitud de alguna palabra que debe escribirse en esa parte, es imposible escribir esta parte del informe en una parte del rollo de tal ancho.
Se garantiza que se puede dibujar una barra vertical para que se puedan escribir ambas partes del informe. Vers quiere dibujar una línea vertical para que la longitud del rollo, que es suficiente para escribir un informe, sea mínima. Ayúdala a encontrar la longitud mínima.
Entrada:
- la primera línea contiene tres números enteros w, n y m — ancho de rollo, número de palabras en la primera y segunda parte del informe (\(1 <= w <= 10^9\); \(1 <= n, m <= 100 000\));
- la siguiente línea da n enteros ai — longitud de la i-ésima palabra de la primera parte del informe \(1 <= a_i <= 10^9\);
- la siguiente línea da m enteros bj — longitud de la jésima palabra de la segunda parte del informe \(1 <= b_j <= 10^9\).
Se garantiza que es posible trazar una línea para que se puedan escribir ambas partes del informe.
Entrada: en una sola línea, imprime un solo número entero — la longitud mínima del rollo, que es suficiente para escribir un informe.
Ejemplos
| # |
Entrada |
Salida |
| 1 |
15 6 6
2 2 2 3 2 2
3 3 5 2 4 3
|
3 |
Nota
En la prueba de muestra, el rollo se puede dividir en dos partes dibujando una línea entre la séptima y la octava columna de celdas y luego escribiendo dos palabras por línea en ambas partes del informe.