Organisation des vacances – Qualification 2018

Level 3

Énoncé

Joseph Marchand est incapable de vendre ses crêpes tout seul sur la plage, et se fait donc aider par ses deux enfants. Cependant, ces derniers aimeraient bien visiter leurs grands-parents en guise de vacances, mais Joseph désire absolument faire grandir son stand de crêpes. Il accepte finalement de leur accorder des vacances, sous quelques conditions.

Tout d'abord, puisque Joseph a besoin de leur aide, il est nécessaire qu'au moins l'un d'eux soit présent à tout moment pour l'assister avec les crêpes (Joseph Marchand tolère cependant que l'un parte et l'autre revienne le même jour). De plus, vu qu'au sein de la famille les crêpes sont sacrées, tout l'argent de Joseph est investi dans le stand, ce qui signifie qu'il souhaite que la somme totale des deux voyages soit minimum.

Malheureusement Joseph est débordé par toutes les possibilités de voyage, et a besoin de votre aide pour faire son choix.

Entrée

La première ligne contient un seul entier $N$, représentant le nombre d'intervalles de vacances à la disposition de Joseph. Les $N$ lignes suivantes décrivent donc chacune un intervalle à l'aide de 3 entiers : $d$, $f$, et $c$, où $d$ est la date de début des vacances, $f$ la fin, et $c$ le coût total de ce voyage.

Sortie

Vous devrez afficher en sortie la somme minimale d'argent que devra dépenser Joseph, ou bien -1 dans le cas où il n'est pas possible pour ses enfants de respecter les conditions imposées.

Contraintes

  • $1 \le N \le 100$
  • $1 \le d \lt f \le 10^7$
  • $1 \le c \le 10^7$

Contraintes de performance

  • $1 \le N \le 10^5$

Runtime constraints

Maximum memory usage
10000 kilobytes
Maximum execution time
300 milliseconds

Input/output samples

Sample input
5
6 10 3
2 5 1
6 7 3
5 8 6
1 3 2
Sample output
4
Note

En utilisant l'intervalle commençant à 2 et finissant à 5 coûtant 1, ainsi que l'intervalle commençant à 6 et finissant à 7 (coûtant 3), on obtient bien un total de 4. On ne peut pas trouver un prix total inférieur. Notez qu'on peut aussi utiliser l'intervalle allant de 6 à 10 et de prix 3 qui nous donne le même résultat final.

Sample input
3
1 4 4
2 5 1
3 6 2
Sample output
-1
Note

Impossible de trouver deux intervalles qui ne se croisent pas. La réponse renvoyée est donc -1.

Submit your solution

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