Tarefas e prazos
Dadas
n tarefas com os respetivos prazos (deadlines) e o lucro que se obtém por completá-las antes do prazo, queremos determinar qual é o lucro total máximo que se pode alcançar. Cada tarefa leva 1 dia a ser concluída. Se uma tarefa não for terminada antes do seu prazo, não se recebe nada.Parte-se do dia 1. Qual é o montante máximo de lucro que se pode obter?
Entrada
A primeira linha da entrada contém um único inteiro
n (1 ≤ n ≤ ), que representa o número de tarefas.As próximas
n linhas contêm pares de inteiros separados por espaço, (1 ≤ , ≤ ), onde é o prazo (deadline) e é o lucro por completar essa tarefa.Saída
O programa deve imprimir o maior lucro total que se pode obter.
Exemplos
Entrada | Saída |
4
4 10
1 3
2 7
2 3 | 20 |
5
1 1
4 100
4 200
4 300
4 200 | 800 |
Explicação
- 10 + 3 + 7
- Primeiro, realiza-se a tarefa cujo prazo (deadline) é 1 ⇒ lucro de 3
- Depois, realiza-se a tarefa cujo prazo é 2 ⇒ lucro de 7
- E por fim, a tarefa com prazo 4 ⇒ lucro de 10
- 100 + 200 + 300 + 200 (apenas tarefas com deadline 4)
- Realiza-se a tarefa com lucro de 100
- Realiza-se a tarefa com lucro de 200
- Realiza-se a tarefa com lucro de 300
- Realiza-se a tarefa com lucro de 200
Constraints
Time limit: 2 seconds
Memory limit: 512 MB
Output limit: 1 MB