Problem
Na Olimpíada Interregional de Programação de Robôs, as competições são realizadas em uma rodada e em um formato incomum. As tarefas são dadas aos participantes sequencialmente, não todas logo no início da rodada, e cada i-ésima tarefa (1 ≤ i ≤ n) fica disponível para os participantes em seu momento s
i. Ao receber a próxima tarefa, cada participante deve determinar imediatamente se a resolverá ou não. Se ele optar por resolver esse problema, ele terá t
i minutos para enviar sua solução para verificação e, durante esse tempo, não poderá passar para a solução de outro problema. Se o participante se recusar a resolver esse problema, ele não poderá voltar a ele no futuro. No momento em que terminar o tempo destinado à tarefa que o participante está resolvendo, ele pode começar a resolver outra tarefa que ficou disponível no mesmo momento, se houver tal tarefa, ou esperar que outra tarefa apareça. Ao mesmo tempo, pela solução correta do i-ésimo problema, o participante recebe c
i pontos.
Artur, que representa um dos centros regionais de inteligência artificial na Olimpíada inter-regional, entende que não só a capacidade de resolver problemas, mas também o cálculo estratégico correto de quais problemas precisam ser resolvidos e quais devem ser ignorados, desempenha um papel importante na tal Olimpíada. Ele, como todos os participantes, antes do início do passeio sabe em que momento cada tarefa ficará disponível, quanto tempo será alocado para sua solução e quantos pontos você pode obter por resolvê-la. Artur é um aluno talentoso e por isso será capaz de resolver com sucesso qualquer problema que escolher resolver na Olimpíada no tempo previsto e passar na verificação.
É necessário escrever um programa que determine o número máximo de pontos que Arthur pode obter com a escolha ótima dos problemas que ele resolverá, bem como o número e a lista de tais problemas.
Entrada
A primeira linha contém um inteiro n (1 ≤ n ≤ 10
5) o número de problemas na Olimpíada.
As próximas n linhas contêm descrições dos problemas, três números em cada linha: si o momento em que o i-ésimo problema aparece em minutos, t
i o tempo alocado para sua solução em minutos e ci quantos pontos que o participante receberá por resolver este problema (1 ≤ s
i, t
i, c
i ≤ 10
9< /sup>).
Impressão
Primeira linha deve conter um único número – o número máximo de pontos que Arthur pode obter na Olimpíada.
A segunda linha deve conter um inteiro m - o número de tarefas a serem resolvidas com a escolha ótima.
A terceira linha deve conter m inteiros separados por espaços - os números desses problemas na ordem em que foram resolvidos. As tarefas são numeradas, começando de um, na ordem em que são descritas no arquivo de entrada.
Se houver várias respostas ótimas, imprima qualquer uma delas.
Exemplos
| # |
Entrada |
Saída |
| 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 |