Prologin
2025
É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