Poids en champignons – Regional event 2017

Level 4

É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$

Runtime constraints

Maximum memory usage
10000 kilobytes
Maximum execution time
1000 milliseconds

Input/output samples

Sample input
4 48
8 12 12 16
Sample output
OUI
Sample input
5 100
1 15 20 88 113
Sample output
NON

Submit your solution

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