Space Bus – Épreuve régionale 2020

Niveau 4

Énoncé

Les compagnies de transport sont en grève ! Et cela même dans l'espace où les agents de la compagnie TSHIRT (Transport Sidéral et Hyperspatial Intergalactique du Réseau Terrestre) bloquent l'entièreté du trafic des transports en commun.

Pourtant, le plus grand événement de la carrière de Joseph Marchand est sur le point de démarrer : le concours de la plus grande pizza faite en apesanteur ! De plus en plus d'inscrits se désistent à cause des spatiobus absents.

Pour ne pas que cet événement soit un désastre, Joseph décide de prendre son mini-spatiobus pour aller chercher lui-même les candidats s'étant inscrits à leurs arrêts de bus respectifs. Malheureusement, le temps lui est compté. En effet, le concours démarre bientôt et tout le monde n'aura pas la chance d'être emmené à temps.

De plus, afin d'éviter les bouchons au bureau de présence, l'administration demande à Joseph d'aller chercher un groupe à la fois à son arrêt avant de passer à un autre groupe.

Il faut maintenant agir de façon organisée de sorte qu'un maximum de candidats puissent arriver avant que le concours ne commence. Heureusement, grâce à la fiche d'inscription, Joseph sait combien de candidats attendent à chaque station et combien de temps il met à faire un aller-retour entre le centre du concours et la station en question.

Entrée

  • Sur la première ligne, un entier $N$ représentant le nombre de stations à visiter.
  • Sur la deuxième ligne, $N$ entiers indiquant le nombre de personnes à prendre dans chaque station.
  • Sur la troisième ligne, $N$ entiers représentant le temps d'un aller-retour entre le centre et la station.
  • Sur la quatrième ligne, un entier $M$ représentant le temps total dont Joseph Marchand dispose.

Sortie

Le nombre maximum de candidats que Joseph peut emmener dans sa limite de temps.

Contraintes

  • 1 ≤ N ≤ 30
  • 1 ≤ M ≤ 1000

Contraintes de performance

  • 1 ≤ N ≤ 500
  • 1 ≤ M ≤ 10000

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
3
5 2 3
10 7 13
23
Exemple de sortie
8
Commentaire

Au maximum, Joseph pourra prendre les passagers de la première station (5) et ceux de la 3ème station (3) pour un temps total de 23 minutes soit sa limite de temps. Il peut donc emmener au maximum 8 personnes au concours.

Exemple d'entrée
5
7 7 4 11 5
15 9 10 20 15
35
Exemple de sortie
18
Commentaire

Soit Joseph peut prendre les passagers des stations 1, 2 et 3 pour un total de 34 minutes soit prendre les passagers des stations 1 ou 2 et 4 pour un total de 35 ou 29 minutes. Ces trois chemins permettent de prendre un total de 18 personnes.