Problem
Vers doit préparer un rapport sur la dernière sortie. Elle a déjà composé le texte dans sa tête, il ne reste plus qu'à l'écrire. Le rapport sera composé de deux parties : la première contiendra n mots, ith dont ai< / code> lettres, la seconde — m mots, dont le jième est composé de bj lettres. La langue Kriya ne contient aucun signe de ponctuation. Vers doit rédiger le rapport sur un rouleau de papier quadrillé, w cellules de large. Puisque le rapport se compose de deux parties, elle divisera le rouleau en deux parties de toute la largeur avec une ligne verticale, après quoi elle écrira la première partie du côté gauche, et du côté droit — seconde.
Les deux parties du rapport sont rédigées de la même manière, chacune sur sa propre partie du rôle. Une lettre du mot occupe exactement une cellule. Le premier mot est écrit dans la première ligne du rouleau, à partir de la cellule la plus à gauche de cette partie du rouleau. Chaque mot suivant, si possible, doit être écrit sur la même ligne que le précédent et en être séparé par exactement une cellule vide.
Sinon, il est écrit sur la ligne suivante, en partant de la cellule la plus à gauche. Si la largeur d'une partie du rouleau est inférieure à la longueur d'un mot qui doit être écrit dans cette partie, il est impossible d'écrire cette partie du rapport sur une partie du rouleau d'une telle largeur.
Il est garanti qu'une barre verticale peut être dessinée afin que les deux parties du rapport puissent être écrites. Vers souhaite tracer une ligne verticale afin que la longueur du rouleau, suffisante pour rédiger un rapport, soit minimale. Aidez-la à trouver cette longueur minimale.
;
Entrée :
- la première ligne contient trois entiers w, n et m — largeur du rouleau, nombre de mots dans les première et deuxième parties du rapport (\(1 <= w <= 10^9\) ; \(1 <= n, m <= 100 000\));
- la ligne suivante donne n entiers ai — longueur du ième mot de la première partie du rapport \(1 <= a_i <= 10^9\);
- la ligne suivante donne m entiers bj — longueur du jème mot de la deuxième partie du rapport \(1 <= b_j <= 10^9\).
Il est garanti qu'il est possible de tracer une ligne afin que les deux parties du rapport puissent être écrites.
Saisie : sur une seule ligne, imprimez un seul entier — la longueur minimale du rouleau, suffisante pour rédiger un rapport.
Exemples
| # |
Entrée |
Sortie |
| 1 |
15 6 6
2 2 2 3 2 2
3 3 5 2 4 3
3 |
Remarque
Dans l'exemple de test, le rouleau peut être divisé en deux parties en traçant une ligne entre la 7e et la 8e colonne de cellules, puis en écrivant deux mots par ligne dans les deux parties du rapport.