Cambriolage – Qualification 2013

Level 2

Énoncé

Vous possédez un jeu de clés passe-partout. Ayant minutieusement préparé le cambriolage de cette nuit, vous connaissez déjà les caractéristiques des serrures auxquelles vous allez vous attaquer (ancienneté et niveau de sécurité) et les limites de vos passe-partout : un passe-partout est dit de force (xi, yi) s'il peut ouvrir les serrures datées d'avant 1990 (aussi dites « traditionnelles ») de sécurité au plus xi et les serrures datées de 1990 ou après (aussi dites « rectifiées ») de sécurité au plus yi.

Vous savez, de votre longue expérience de cambrioleur professionnel, que le temps de l'opération est un facteur décisif : pas question donc de trimbaler toutes sortes de clés inutiles. Vous cherchez à savoir le nombre minimal de passe-partout à emporter pour pouvoir ouvrir toutes les serrures. S'il est impossible de toutes les ouvrir avec votre ensemble de clés, retournez 0.

Entrée

L'entrée comprendra :

  • un nombre N, le nombre de passe-partout que vous possédez ;
  • sur chacune des N lignes suivantes, deux nombres xi et yi, représentant la force de votre i-ème passe-partout ;
  • un nombre M, le nombre de serrures que vous comptez cambrioler ;
  • sur chacune des M lignes suivantes, deux nombres ai et si, correspondant respectivement à l'ancienneté de la serrure (-1 pour « avant 1990 », 1 pour « 1990 ou après ») et au niveau de sécurité de la i-ème serrure.

Sortie

Vous afficherez en sortie :

  • le nombre minimum de passe-partout à emporter pour mener à bien votre tâche si c'est possible, 0 sinon.

Contraintes

  • 1 <= N <= 1 000
  • 1 <= M <= 100 000
  • 1 <= xi, yi, si <= 1 000 000

Runtime constraints

Maximum memory usage
2000 kilobytes
Maximum execution time
1000 milliseconds

Input/output samples

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

Dans cet exemple, le premier passe-partout suffit à passer partout.

Sample input
2
2 5
4 7
3
-1 2
1 6
-1 5
Sample output
0
Note

Ici, la 3<sup>e</sup> serrure résiste à tous les passe-partout.

Sample input
2
3 5
2 7
2
-1 3
1 6
Sample output
2
Note

Enfin, dans cet exemple, les deux passe-partout sont nécessaires pour ouvrir toutes les serrures.

Submit your solution

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