Prologin, le concours national d'informatique

Énoncé¶

La première porte que vous rencontrez est vérouillée par un grand nombre de serrures. Chaque serrure possède un type allant de $1$ à $N$, et il est nécessaire d'avoir autant de clés que de serrures de chaque type pour pouvoir ouvrir la porte.

Par exemple, si la porte possède trois serrures de type 1 et deux serrures de type 2, alors il vous faudra trois clés de type 1 et deux clés de type 2 pour ouvrir la porte.

Heureusement, un serrurier qui se trouvait dans les alentours vous propose d'échanger deux clés d'un même type contre une clé d'un type différent, et à souhait.

Pour toutes les serrures que vous ne pouvez toujours pas ouvrir, il ne vous reste qu'une seule solution : les crocheter.

Vu que crocheter une serrure prend un temps considérable, votre objectif est de déterminer le nombre minimal de serrures que vous devrez crocheter.

Entrée¶

L’entrée contiendra :

Sur la première ligne, un entier : N, le nombre de serrures différentes qui existent.
Sur la ligne suivante, une liste de N entiers séparés par des espaces : serrures, le nombre de serrures de chaque type présentes sur la porte.
Sur la ligne suivante, une liste de N entiers séparés par des espaces : cles, le nombre de clés de chaque type que vous possédez.

Sortie¶

Afficher le nombre de serrures que vous devrez crocheter au minimum.

Contraintes¶

$1 \le N \le 1\,000$

Contraintes d'exécution

Utilisation mémoire maximum: 1000 kilo-octets
Temps d'exécution maximum: 1000 millisecondes

Exemples d'entrée/sortie

Exemple d'entrée

3
2 3 1
4 2 1

Exemple de sortie

Commentaire

Vous pouvez échanger au serrurier vos deux clés de type 1 en trop pour une clé de type 2. Vous aurez alors suffisamment de clés pour ouvrir la porte sans crocheter une seule serrure.