Problem
Vers precisa preparar um relatório sobre a última surtida. Ela já compôs o texto em sua cabeça, resta apenas escrevê-lo. O relatório consistirá em duas partes: a primeira conterá n palavras, iª das quais consiste em ai< / code> letras, o segundo — m palavras, a jésima das quais consiste em letras bj. A linguagem Kriya não contém sinais de pontuação. Vers deve escrever o relatório em um rolo de papel quadriculado, w células de largura. Como o relatório consiste em duas partes, ela dividirá o rolo em duas partes de toda a largura com uma linha vertical, após o que escreverá a primeira parte no lado esquerdo e no lado direito — segundo.
Ambas as partes do relatório são escritas da mesma forma, cada uma em sua parte do rolo. Uma letra da palavra ocupa exatamente uma célula. A primeira palavra é escrita na primeira linha do rolo, começando na célula mais à esquerda desta parte do rolo. Cada palavra seguinte, se possível, deve ser escrita na mesma linha da anterior e separada dela por exatamente uma célula vazia.
Caso contrário, é escrito na próxima linha, começando na célula mais à esquerda. Se a largura de uma parte do rolo for menor que o comprimento de alguma palavra que deveria ser escrita nessa parte, é impossível escrever essa parte do relatório em uma parte do rolo com essa largura.
É garantido que uma barra vertical pode ser desenhada para que ambas as partes do relatório possam ser escritas. Vers deseja traçar uma linha vertical para que o comprimento do rolo, suficiente para escrever um relatório, seja mínimo. Ajude-a a encontrar esse comprimento mínimo.
Entrada:
- a primeira linha contém três inteiros w, n e m — largura do rolo, número de palavras na primeira e segunda partes do relatório (\(1 <= w <= 10^9\); \(1 <= n, m <= 100 000\));
- a próxima linha fornece n inteiros ai — comprimento da i-ésima palavra da primeira parte do relatório \(1 <= a_i <= 10^9\);
- a próxima linha fornece m inteiros bj — comprimento da jésima palavra da segunda parte do relatório \(1 <= b_j <= 10^9\).
É garantido que é possível traçar uma linha para que as duas partes do relatório possam ser escritas.
Entrada: em uma única linha imprima um único inteiro — o comprimento mínimo do rolo, o que é suficiente para escrever um relatório.
Exemplos
| # |
Entrada |
Saída |
| 1 |
15 6 6
2 2 2 3 2 2
3 3 5 2 4 3
|
3 |
Nota
No teste de amostra, o rolo pode ser dividido em duas partes desenhando uma linha entre a 7ª e a 8ª coluna de células e, em seguida, escrevendo duas palavras por linha em ambas as partes do relatório.