Marché nocturne – Qualification 2020

Niveau 3

Énoncé

Entre certaines missions vous prenez du temps pour vous balader dans les marchés extra-terrestres, un événement qui vous fascine tout particulièrement, pour son incroyable mélange de culture et de curiosité venu de toutes les galaxies. Cela sera l'occasion de ramener un souvenir de votre dernière mission P.A.N.D.A (Parachutage Auto Négociant la Descente Astrale).

Vous avez repéré un marchand de minerai rare et inconnu de la planète Terre. En tant que fin connaisseur des cultures extra-terrestres, vous êtes évidemment au courant de la coutume locale, et de l'importance de la contigüité. Pour faire plaisir au vendeur (qui semble grincheux et légèrement xénophobe), vous vous appliquez donc pour choisir uniquement des minerais contigus sur le fil.

Pour éviter que ce souvenir prenne trop de place, vous souhaitez choisir un nombre minimal de minerai, toujours contigus sur le fil, tel que la somme de leurs prix soit exactement égale à votre budget cadeau $B$.

Entrée

Sur la première ligne un entier $N$ indiquant le nombre de minerai rare.

La deuxième ligne est constituée de $N$ entiers séparés par des espaces, représentant le prix de chaque minerai.

Enfin, la dernière ligne contient $B$, le total d'argent que vous souhaitez dépenser dans ce souvenir.

Sortie

Le nombre minimal de minerai que vous rapporterez, ou -1 si ce n'est pas possible de résoudre le problème.

Contraintes

  • $1 ≤ N ≤ 100$
  • $0 ≤ prix ≤ 100$
  • $1 ≤ B ≤ 10000$

Contraintes de performance

  • $1 ≤ N ≤ 10^6$
  • $1 ≤ B ≤ 10^8$

Contraintes d'exécution

Utilisation mémoire maximum
40000 kilo-octets
Temps d'exécution maximum
1000 millisecondes

Exemples d'entrée/sortie

Exemple d'entrée
6
4 7 3 10 1 9
14
Exemple de sortie
3
Commentaire

En prenant les 3 premiers minerais, le total est exactement de 14 (4 + 7 + 3). Une autre solution serait de prendre les minerais valant 3, 10 et 1. Attention, on ne peut pas prendre uniquement les minerais valant 4 et 10 car la sélection de minerais n'est pas contigüe !

Exemple d'entrée
5
4 0 3 9 1
8
Exemple de sortie
-1
Commentaire

Impossible de trouver une sélection contigüe de minerais dont la somme des prix est égale à 8. Vous pouvez avoir 7 en additionnant 4 + 0 + 3, mais pas 8.