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