Prologin, le concours national d'informatique

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

Contraintes d'exécution

Utilisation mémoire maximum: 100 kilo-octets
Temps d'exécution maximum: 100 millisecondes

Exemples d'entrée/sortie

Exemple d'entrée

Exemple de sortie

Commentaire

Ici le coût de chaque modèle de véhicules est le suivant :

$50 + 100 * 6 = 650€$
$70 + 100 * 4 = 470€$

Le troisième modèle est d'office éliminé car son réservoir n'est pas assez grand. Le choix se fait donc entre les deux premiers modèles et nous pouvons donc constater que le modèle 2 est plus économique que le premier.