Chez le loueur – Regional event 2022

Level 1

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

Runtime constraints

Maximum memory usage
100 kilobytes
Maximum execution time
100 milliseconds

Input/output samples

Sample input
3
100
1 50 103 6
2 70 200 4
3 20 15 1
Sample output
2
Note

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.

Sample input
0
42
Sample output
-1
Note

Ici, aucun véhicule ne permettrait à Joseph Marchand de faire son trajet. Nous devons donc afficher $-1$.

Submit your solution

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