Attività e scadenze
Date
n attività con le rispettive scadenze (deadline) e il profitto che si ottiene completando ciascuna prima della scadenza, si desidera determinare qual è il profitto totale massimo ottenibile. Ogni attività richiede 1 giorno per essere completata. Se un’attività non viene completata prima della sua scadenza, non si guadagna nulla.Si parte dal giorno 1. Quanto profitto è possibile ottenere?
Input
La prima riga dell’input contiene un unico intero
n (1 ≤ n ≤ ), che indica il numero di attività.Le successive
n righe contengono coppie di interi (1 ≤ , ≤ ) separate da uno spazio, dove è la scadenza per l’attività i-esima e è il profitto ottenuto completandola in tempo.Output
Il programma deve stampare il profitto totale massimo ottenibile.
Esempi
Input | Output |
4
4 10
1 3
2 7
2 3 | 20 |
5
1 1
4 100
4 200
4 300
4 200 | 800 |
Spiegazione
- 10 + 3 + 7
- Prima, eseguire l’attività con scadenza 1 ⇒ si guadagnano 3
- Poi, eseguire l’attività con scadenza 2 ⇒ si guadagnano 7
- Infine, eseguire l’attività con scadenza 4 ⇒ si guadagnano 10
- 100 + 200 + 300 + 200 (vengono eseguite solo le attività con scadenza 4)
- Eseguire l’attività con profitto 100
- Eseguire l’attività con profitto 200
- Eseguire l’attività con profitto 300
- Eseguire l’attività con profitto 200
Constraints
Time limit: 2 seconds
Memory limit: 512 MB
Output limit: 1 MB