Marché nocturne – Qualification 2020

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

Runtime constraints

Maximum memory usage
40000 kilobytes
Maximum execution time
1000 milliseconds

Input/output samples

Sample input
6
4 7 3 10 1 9
14
Sample output
3
Note

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 !

Sample input
5
4 0 3 9 1
8
Sample output
-1
Note

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.

Submit your solution

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