La Grande Fuite – Épreuve régionale 2019

Niveau 5

Énoncé

Martin construit une arche pour les animaux de la savane. Malheureusement il ne pourra pas abriter tous le monde sur son arche qui ne peut supporter qu'un poids limité.

Martin connait le poids de tous les animaux. Il sait aussi parmis tous les habitants de la savane lesquels sont amis et qu'aucun d'entre eux ne se permettrait de monter sans avoir l'assurance que tous ses amis y auront une place.

Martin veut savoir quel est le nombre maximal d'animaux qu'il arrivera à abriter sur son arche.

Entrée

L’entrée contiendra :

  • Sur la première ligne, un entier : $nb$ $animaux$, le nombre d'animaux dans la savane.
  • Sur la ligne suivante, un entier : $capacite$, le poids maximal qui peut être supporté par l'arche.
  • Sur la ligne suivante, une liste de $nb$ $animaux$ entiers séparés par des espaces : $poids$, le poids de chaque animal.
  • Sur la ligne suivante, un entier : $nb$ $amis$, le nombre de paires d'amis.
  • Sur les lignes suivantes, une liste de $nb$ $amis$ éléments : $amis$, les animaux qui sont amis.
    • Une ligne par élément de la liste : séparés par des espaces, un entier $u$ (un animal), et un entier $v$ (un autre animal).

Sortie

Affichez un entier, le nombre maximal d'animaux qui peuvent être abrités sur l'arche de Martin.

Contraintes

  • $1$ ≤ $nb$ $animaux$ ≤ $10000$
  • $1$ ≤ $capacite$ ≤ $50000$
  • $0$ ≤ $poids[i]$ ≤ $50000$
  • $1$ ≤ $nb$ $amis$ ≤ $10000$
  • $1$ ≤ $u$, $v$ ≤ $nb$ $animaux$

Contraintes d'exécution

Utilisation mémoire maximum
10000 kilo-octets
Temps d'exécution maximum
2000 millisecondes

Exemples d'entrée/sortie

Exemple d'entrée
7
12
1 1 2 2 3 3 3
4
1 2
3 4
5 6
5 7
Exemple de sortie
5
Commentaire

Le mieux que Martin puisse faire est de sauver les 5 animaux suivants: 1, 2, 5, 6 et 7. Il ne peut rajouter que 1kg sur son arche, ce qui n'est pas suffisant pour sauver un animal de plus.

Exemple d'entrée
9
9
4 1 2 2 2 1 1 1 1
6
1 2
3 4
4 5
7 6
7 8
6 9
Exemple de sortie
6
Commentaire

Le mieux que Martin puisse faire est de sauver les 6 animaux suivants: 1, 2, 6, 7, 8 et 9. Il ne peut alors plus rajouter de poids sur son arche.

S'il avait par exemple voulu sauver 4, celui-ci aurait imposé que ses deux amis, 3 et 5, soient sauvés. Il ne resterait alors que 3kg disponible sur l'arche. Dans ce cas:

  • il n'y a plus de place pour sauver 2 (1kg) car celui-ci voudrait sauver 1 (4 kg)
  • il n'y a plus de place pour sauver 7 (1kg) car celui-ci voudrait sauver 8 (1kg) et 6 (1kg), ce dernier voudra sauver 9 (1kg)
  • il n'y a plus de place pour sauver 8 (1kg) car celui-ci voudrait sauver 7 (1kg) qui veut sauver 6 (1kg) qui veut sauver 9 (1kg)
  • etc ...