Énoncé¶
Joseph Marchand doit se rendre dans une ville voisine pour une conférence. Malheureusement, son véhicule tombe en panne. Il décide donc en urgence de se rendre chez un loueur de véhicules. Ce dernier lui propose $N$ modèles de véhicules, chacun avec un prix initial $P$ et un coût au kilomètre $C$. De plus, en prévoyant son trajet, Joseph remarque qu’il ne pourra pas faire le plein durant le trajet et le véhicule devra donc posséder un réservoir $R$ suffisant pour tenir tout le trajet. On considérera qu’un litre d’essence est nécessaire pour parcourir un kilomètre. Aidez Joseph à choisir le modèle $M$ de véhicule le plus économique pour son déplacement.
Entrée¶
L’entrée contiendra :
- Sur la première ligne, un entier : N, le nombre de véhicules disponibles.
- Sur la ligne suivante, un entier : D, la distance à parcourir.
- Sur les lignes suivantes, une liste de N éléments : V, la liste des
véhicules.
- Une ligne par élément de la liste : séparés par des espaces, un entier M (le numéro de série du véhicule), un entier P (le prix initial), un entier R (la taille du réservoir), et un entier C (le coût au kilomètre).
Sortie¶
Le numéro de modèle du véhicule revenant le moins cher ou $-1$ si aucun véhicule n'est disponible (la liste est vide ou aucun véhicule ne possède un réservoir suffisamment grand). Si deux modèles sont équivalents, le véhicule retenu sera celui ayant été considéré en premier dans l'ordre de la liste.
Contraintes¶
- $0 \le N \le 200$
- $1 \le D \le 500$
Contraintes de performance¶
- $0 \le N \le 10\,000$