Escalonamento de Tarefas

#180
Made by: Crazynds
100MB
0.1s

Você tem $N$ tarefas para executar. Cada tarefa $i$ possui:

  • Um prazo $d_i$: a tarefa deve ser completada no slot de tempo $\le d_i$.
  • Um lucro $p_i$: recebido ao completar a tarefa dentro do prazo.

Cada tarefa ocupa exatamente 1 unidade de tempo. Você pode executar no máximo uma tarefa por unidade de tempo e os slots são numerados $1, 2, 3, \ldots$

Selecione um subconjunto de tarefas e agende-as para maximizar o lucro total, respeitando os prazos.

Input

A primeira linha contém um inteiro $N$ $(1 \le N \le 10^5)$.

As próximas $N$ linhas contêm dois inteiros $d_i$ e $p_i$ $(1 \le d_i \le 10^9,\ 1 \le p_i \le 10^9)$.

Output

Imprima um único inteiro: o lucro máximo obtível.

Input Example
Output Example 
5
2 20
1 15
2 10
1 5
3 1
36

Explanation 1:
Agendando: - Slot 1: tarefa 2 (lucro 15) - Slot 2: tarefa 1 (lucro 20) - Slot 3: tarefa 5 (lucro 1) Lucro total $= 36$. A tarefa 3 (lucro 10, prazo 2) não cabe mais pois os slots 1 e 2 já estão ocupados pelas tarefas mais lucrativas. 

4
1 10
1 20
1 30
1 5

30

3
100 50
100 30
100 10

90

5
5 1
4 2
3 3
2 4
1 5

15