Cambriolage – Qualification 2013

É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 (x_i, y_i) s'il peut ouvrir les serrures datées d'avant 1990 (aussi dites « traditionnelles ») de sécurité au plus x_i et les serrures datées de 1990 ou après (aussi dites « rectifiées ») de sécurité au plus y_i.

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 x_i et y_i, 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 a_i et s_i, 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 <= x_i, y_i, s_i <= 1 000 000