Porte crochetée – Regional event 2022

Level 1

É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$

Runtime constraints

Maximum memory usage
1000 kilobytes
Maximum execution time
1000 milliseconds

Input/output samples

Sample input
3
2 3 1
4 2 1
Sample output
0
Note

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.

Sample input
3
1 2 3
4 3 1
Sample output
1
Note

Vous pouvez ici échanger deux de vos quatre clés de type 1 en une clé de type 3. Il ne vous manquera plus qu'une serrure de type 3 que vous devrez crocheter pour ouvrir la porte.

Submit your solution

You have to register or log in to be able to submit your solution.