Problem
En la Olimpiada Interregional de Programación de Robots, las competencias se llevan a cabo en una ronda y en un formato inusual. Las tareas se dan a los participantes secuencialmente, no todas al comienzo de la ronda, y cada i-ésima tarea (1 ≤ i ≤ n) está disponible para los participantes en su momento s
i. Al recibir la siguiente tarea, cada participante debe determinar inmediatamente si la resolverá o no. Si elige resolver este problema, entonces tiene t
i minutos para enviar su solución para verificación, y durante este tiempo no puede pasar a resolver otro problema. Si el participante se niega a resolver este problema, en el futuro no podrá volver a él. En el momento en que finaliza el tiempo asignado a la tarea que el participante está resolviendo, puede comenzar a resolver otra tarea que quedó disponible en el mismo momento, si existe tal tarea, o esperar a que aparezca otra tarea. Al mismo tiempo, por la correcta solución del i-ésimo problema, el participante recibe c
i puntos.
Artur, quien representa a uno de los centros regionales de inteligencia artificial en la Olimpiada interregional, entiende que no solo la capacidad de resolver problemas, sino también el correcto cálculo estratégico de qué problemas hay que resolver y cuáles omitir, juega un papel importante en tal Olimpiada. Él, como todos los participantes, antes del inicio del recorrido sabe en qué momento estará disponible cada tarea, cuánto tiempo se asignará para su solución y cuántos puntos puede obtener por resolverla. Artur es un estudiante talentoso y, por lo tanto, podrá resolver con éxito cualquier problema que decida resolver en la Olimpiada en el tiempo asignado y aprobar la verificación.
Se requiere escribir un programa que determine el número máximo de puntos que Arthur puede obtener con la elección óptima de los problemas que resolverá, así como el número y la lista de tales problemas.
Entrada
La primera línea contiene un número entero n (1 ≤ n ≤ 10
5) el número de problemas en la Olimpiada.
Las siguientes n líneas contienen descripciones de los problemas, tres números en cada línea: si el momento en que aparece el i-ésimo problema en minutos, t
i el tiempo asignado para su solución en minutos, y ci cuántos puntos que recibirá el participante por resolver este problema (1 ≤ s
i, t
i, c
i ≤ 10
9< /sup>).
Impresión
Primera línea debe contener un solo número – el número máximo de puntos que Arthur puede obtener en la Olimpiada.
La segunda línea debe contener un entero m: la cantidad de tareas que se resolverán con la opción óptima.
La tercera línea debe contener m enteros separados por espacios: los números de estos problemas en el orden en que se resolvieron. Las tareas están numeradas, comenzando desde uno, en el orden en que se describen en el archivo de entrada.
Si hay varias respuestas óptimas, imprima cualquiera de ellas.
Ejemplos
| # |
Entrada |
Salida |
| 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 |