Mise en boîte – Qualification 2023

Level 2

Énoncé

Nos 6 amis sont toujours en train de choisir leur film quand Cyril se rend compte que les restes du repas qu'ils ont dégusté juste avant attendent encore sur la table basse. Pour conserver leurs aliments, il faut les mettre dans des boîtes et les ranger au réfrigérateur. Qui sait, ils pourraient en avoir besoin si d'aventure ils décidaient de se lancer dans un grand voyage ! Le hasard faisant bien les choses, ils ont autant de boîtes que de restes. Tous les récipients ne sont toutefois pas forcément de la bonne taille.

Aidez nos 6 amis à remplir le plus de boîtes sachant qu'un aliment d'un certain volume ne peut entrer que dans une boîte d'un volume supérieur ou égal. Afin de conserver au mieux le goût de la nourriture, on ne mettra qu'un aliment dans chaque boîte.

Entrée

L’entrée contiendra :

  • Sur la première ligne, un entier : N, le nombre de boîtes et de restes.
  • Sur la ligne suivante, une liste de N entiers séparés par des espaces : restes, Liste des volumes des restes.
  • Sur la ligne suivante, une liste de N entiers séparés par des espaces : boîtes, Liste des volumes des boîtes.

Sortie

Afficher sur une ligne le nombre maximum de restes que l'on peut mettre en boîte.

Contraintes

  • $1 \le N \le 100$
  • $0 \le restes[ ] \le 1\,000\,000\,000$
  • $0 \le boîtes[ ] \le 1\,000\,000\,000$

Contraintes de performance

  • $1 \le N \le 100\,000$

Runtime constraints

Maximum memory usage
100000 kilobytes
Maximum execution time
1000 milliseconds

Input/output samples

Sample input
3
832 342 500
750 250 500
Sample output
2
Note

Ici on peut mettre l'aliment de 500 cm³ dans la boîte de 500 cm³. Le reste de 342 cm³ peut être rangé dans la boîte de 750 cm³.

Sample input
5
487 601 584 819 601
750 500 700 650 700
Sample output
4
Note

Voici une liste possible de paires (reste, boîte) : (487, 500), (584, 650), (601, 700), (601, 700). On aurait pu également mettre un aliment de 601 cm³ dans la boîte de 750 cm³. Le mets de 819 cm³ ne peut être mis en boîte.

Submit your solution

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