Prologin
2024
Énoncé¶
Il y a, près de chez Joseph Marchand, une forêt où poussent de très nombreuses variétés de champignons. On peut entre autres y trouver beaucoup d'espèces de champignons géants.
Joseph est très friand de champignons, et il décide ce matin d'aller à la cueillette et de ramasser un maximum de champignons différents.
De retour chez lui en début d'après-midi, Joseph a ramené $N$ champignons (il en a cueilli en réalité un peu plus, mais comme il n'avait pas pris de petit-déjeuner, tellement il était envieux d'aller à la cueillette, il en a mangé quelques uns sur la route).
Joseph se demande alors, en voyant la taille immense des champignons cueillis, s'il ne pourrait pas à tout hasard se peser uniquement à l'aide des champignons, c'est à dire de trouver un sous-ensemble des champignons dont la somme des poids est égal à son propre poids.
Expert en champignons, Joseph possède un cahier dans lequel il a répertorié l'ensemble des champignons poussant dans la région, il connaît donc leurs poids facilement grâce à ce cahier (il faut savoir que tous les champignons d'une même espèce ont exactement le même poids).
Il vous donne donc les poids de chaque champignon recueilli $c_i$, ainsi que son propre poids $P$ et il vous demande de l'aider en déterminant s'il est possible de le peser uniquement avec ces champignons.
Note : bien sûr, étant donné que Joseph a ramené plein de champignons géants, dont certains sont même plus lourds que lui, il n'y est pas allé avec un simple panier, il a loué une grue adaptée hier soir en ville.
Entrée¶
L'entrée comprendra deux lignes :
- La première ligne contiendra deux entiers $N$ et $P$, le nombre de champignons que Joseph a cueillis et son propre poids.
- La deuxième ligne contiendra $N$ entiers, le i-ème d'entre eux désignant le poids du i-ème champignon.
Sortie¶
Vous afficherez « OUI » si Joseph peut être pesé à l'aide de champignons, et « NON » sinon.
Contraintes¶
- $1 \le N \le 10$
- $1 \le P \le 100$
- $1 \le c_i \le 20$
Contraintes de performance¶
- $1 \le N \le 1\ 000$
- $1 \le P \le 2\ 000$
- $1 \le c_i \le 10\ 000$