Choisissez vos armes

Vous avez la reçu la mission de débarrasser le royaume de tous les monstres qui l'habitent. Il y a deux types de monstres, les grands monstres squelettiques et les petits monstres grassouillets.

Pour tuer un grand monstre squelettique, il vous faut une épée suffisamment longue. La longueur exacte dépend du monstre en question. Pour tuer un petit monstre grassouillet, il vous faut une épée suffisamment solide, et donc suffisamment large. La largeur exacte dépend là encore du monstre considéré.

Vous avez bien étudié le profil de chacun des monstres habitant le royaume, et vous connaissez donc le type de chaque monstre ainsi que la longueur ou bien la largeur minimum d'une épée qui peut le tuer.

Vous vous rendez maintenant à l'armurerie pour vous équiper. On vous y propose un ensemble d'épées, chaque épée étant d'une certaine longueur et d'une certaine largeur. Quel est le nombre minimum d'épées qu'il vous faut acheter afin de pouvoir tuer tous les monstres ? Notez qu'il se peut que cette mission soit impossible.

• 1 <= L <= 10 000, où L décrit une largeur ou une longueur (en millimètres).
• 1 <= N <= 10 000, où N est le nombre de monstres.
• 1 <= P <= 10 000, où P est le nombre d'épées proposées.

Les N lignes suivantes décrivent les monstres un par un. Chacune contient ainsi deux entiers séparés par un espace :

• Le premier entier vaut 0 pour un grand monstre squelettique et 1 pour un petit monstre grassouillet.
• Le second entier donne la longueur minimale (pour un grand monstre) ou la largeur minimale (pour un petit monstre) d'une épée tuant ce monstre.

La ligne suivante contient un entier : P.

Les P lignes suivantes décrivent les épées une par une. Chacune contient ainsi deux entiers séparés par un espace :

• Le premier entier décrit la longueur de l'épée.
• Le second entier décrit la largeur de l'épée.

Vous devez afficher exactement un entier sur une ligne, représentant le nombre minimal d'épées à acheter pour pouvoir tuer tous les monstres, ou bien -1 si c'est impossible.

• Un petit monstre grassouillet nécessitant une épée de largeur 6 ou plus
• Un grand monstre squelettique nécessitant une épée de longueur 12 ou plus
• Un grand monstre squelettique nécessitant une épée de longueur 18 ou plus
• Un petit monstre grassouillet nécessitant une épée de largeur 4 ou plus

L'armurier vous propose 5 épées différentes :

• Une épée de longueur 14, largeur 7
• Une épée de longueur 9, largeur 3
• Une épée de longueur 1, largeur 1
• Une épée de longueur 18, largeur 2
• Une épée de longueur 7, largeur 15

Squelette de code C++ :

#include <cstdio>
#include <cstdlib>

int main()
{
   // pour lire un nombre dans la variable X, faire :
   int X;
   scanf("%d", &X);
   
   // pour afficher un entier X sur une ligne, faire :
   printf("%d\n", X);

   return 0;
}

let scan_int () = Scanf.scanf " %d" (fun x -> x)
let show_int n = Printf.printf "%d\n" n

let _ = 
   (* votre code ici *)

   (* pour lire un nombre, utilisez la ligne suivante *)
   let x = scan_int() in

   (* pour afficher le nombre x sur une ligne, faire *)
   show_int x;