Algoritmi e Strutture Dati

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

  1. 10 + 3 + 7

    1. Prima, eseguire l’attività con scadenza 1 ⇒ si guadagnano 3

    2. Poi, eseguire l’attività con scadenza 2 ⇒ si guadagnano 7

    3. Infine, eseguire l’attività con scadenza 4 ⇒ si guadagnano 10

  2. 100 + 200 + 300 + 200 (vengono eseguite solo le attività con scadenza 4)

    1. Eseguire l’attività con profitto 100

    2. Eseguire l’attività con profitto 200

    3. Eseguire l’attività con profitto 300

    4. Eseguire l’attività con profitto 200

Constraints

Time limit: 2 seconds

Memory limit: 512 MB

Output limit: 1 MB

To check your solution you need to sign in
Sign in to continue