Problem
Alle Olimpiadi interregionali di programmazione dei robot, le competizioni si svolgono in un round e in un formato insolito. I compiti vengono assegnati ai partecipanti in sequenza, non tutti all'inizio del round, e ogni compito i-esimo (1 ≤ i ≤ n) diventa disponibile per i partecipanti al suo momento s
i. Al ricevimento dell'attività successiva, ogni partecipante deve determinare immediatamente se lo risolverà o meno. Se sceglie di risolvere questo problema, ha t
i minuti per sottoporre la sua soluzione alla verifica e durante questo periodo non può passare alla risoluzione di un altro problema. Se il partecipante rifiuta di risolvere questo problema, in futuro non potrà tornarci. Nel momento in cui il tempo assegnato per l'attività che il partecipante sta risolvendo è terminato, può iniziare a risolvere un'altra attività che si è resa disponibile nello stesso momento, se esiste tale attività, oppure attendere che appaia un'altra attività. Allo stesso tempo, per la corretta soluzione dell'i-esimo problema, il partecipante riceve c
i punti.
Artur, che rappresenta uno dei centri regionali di intelligenza artificiale alle Olimpiadi interregionali, comprende che non solo la capacità di risolvere i problemi, ma anche il corretto calcolo strategico di quali problemi devono essere risolti e quali saltare, gioca un ruolo importante a una tale Olimpiade. Lui, come tutti i partecipanti, prima dell'inizio del tour sa a che punto ogni compito sarà disponibile, quanto tempo sarà assegnato per risolverlo e quanti punti puoi ottenere per risolverlo. Artur è uno studente di talento e quindi sarà in grado di risolvere con successo qualsiasi problema scelga di risolvere alle Olimpiadi nel tempo assegnato e passare per la verifica.
È necessario scrivere un programma che determini il numero massimo di punti che Arthur può ottenere con la scelta ottimale dei problemi che risolverà, nonché il numero e l'elenco di tali problemi.
Inserimento
La prima riga contiene un numero intero n (1 ≤ n ≤ 10
5) il numero di problemi nelle Olimpiadi.
Le successive n righe contengono le descrizioni dei problemi, tre numeri su ciascuna riga: si il momento in cui compare l'i-esimo problema in minuti, t
i il tempo concesso per la sua soluzione in minuti, e ci quanti punti che il partecipante riceverà per aver risolto questo problema (1 ≤ s
i, t
i, c
i ≤ 10
9< /sup>).
Impressum
Prima linea deve contenere un solo numero – il numero massimo di punti che Arthur può ottenere alle Olimpiadi.
La seconda riga dovrebbe contenere un numero intero m - il numero di attività da risolvere con la scelta ottimale.
La terza riga dovrebbe contenere m numeri interi separati da spazi - i numeri di questi problemi nell'ordine in cui sono stati risolti. Le attività sono numerate, a partire da uno, nell'ordine in cui sono descritte nel file di input.
Se ci sono più risposte ottimali, stampane qualcuna.
Esempi
| # |
Input |
Uscita |
| 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 |