Problem
Aux Olympiades interrégionales de programmation de robots, les compétitions se déroulent en un tour et dans un format inhabituel. Les tâches sont données aux participants de manière séquentielle, pas toutes au tout début du tour, et chaque ième tâche (1 ≤ i ≤ n) devient disponible pour les participants à son moment s
i. Dès réception de la tâche suivante, chaque participant doit immédiatement déterminer s'il la résoudra ou non. S'il choisit de résoudre ce problème, alors il a t
i minutes pour soumettre sa solution pour vérification, et pendant ce temps il ne peut pas passer à la résolution d'un autre problème. Si le participant refuse de résoudre ce problème, il ne pourra plus y revenir à l'avenir. Au moment où le temps imparti pour la tâche que le participant est en train de résoudre est terminé, il peut commencer à résoudre une autre tâche devenue disponible au même moment, si une telle tâche existe, ou attendre qu'une autre tâche apparaisse. En même temps, pour la solution correcte du ième problème, le participant reçoit c
i points.
Artur, qui représente l'un des centres régionaux d'intelligence artificielle à l'Olympiade interrégionale, comprend que non seulement la capacité à résoudre des problèmes, mais aussi le calcul stratégique correct des problèmes à résoudre et de ceux à éviter, joue un rôle important à une telle Olympiade. Lui, comme tous les participants, avant le début de la visite, sait à quel moment chaque tâche sera disponible, combien de temps sera alloué pour sa solution et combien de points vous pouvez obtenir pour la résoudre. Artur est un étudiant talentueux et pourra donc résoudre avec succès tout problème qu'il choisira de résoudre à l'Olympiade dans le temps imparti et passer pour vérification.
Il est nécessaire d'écrire un programme qui détermine le nombre maximum de points qu'Arthur peut obtenir avec le choix optimal des problèmes qu'il va résoudre, ainsi que le nombre et la liste de ces problèmes.
Entrée
La première ligne contient un entier n (1 ≤ n ≤ 10
5) le nombre de problèmes dans l'Olympiade.
Les n lignes suivantes contiennent des descriptions des problèmes, trois nombres sur chaque ligne : si le moment où le ième problème apparaît en minutes, t
i le temps alloué pour sa résolution en minutes, et ci combien points que le participant recevra pour avoir résolu ce problème (1 ≤ s
i, t
i, c
i ≤ 10
9< /sup>).
Mentions légales
Première ligne doit contenir un seul numéro – le nombre maximum de points qu'Arthur peut obtenir à l'Olympiade.
La deuxième ligne doit contenir un entier m - le nombre de tâches à résoudre avec le choix optimal.
La troisième ligne doit contenir m entiers séparés par des espaces - les numéros de ces problèmes dans l'ordre dans lequel ils ont été résolus. Les tâches sont numérotées, à partir de un, dans l'ordre dans lequel elles sont décrites dans le fichier d'entrée.
S'il existe plusieurs réponses optimales, imprimez l'une d'entre elles.
Exemples
| # |
Entrée |
Sortie |
| 1 |
2
1 1 1
2 2 2
| 3
2
1 2
|
| 2 |
3
1 2 1
3 2 1
2 4 3
| 3
1
3 |