Tareas y fechas límite
Dado un total de
n tareas con sus fechas límite y la ganancia que obtendrás al completarlas antes de la fecha límite, queremos saber cuál es la máxima ganancia total que puedes obtener. Completar cada tarea lleva 1 día. Si no completas la tarea antes de su fecha límite, no ganas nada.Empiezas desde el día 1. ¿Cuánto beneficio puedes obtener?
Entrada
La primera línea de la entrada contiene un solo número entero
n (1 ≤ n ≤ ), que representa la cantidad de tareas.Las siguientes
n líneas contienen parejas de enteros separados por espacio (1 ≤ , ≤ ), donde la primera cifra es la fecha límite y la segunda, la ganancia de completar esa tarea.Salida
El programa debe imprimir la ganancia total máxima que puedes obtener.
Ejemplos
Entrada | Salida |
4
4 10
1 3
2 7
2 3 | 20 |
5
1 1
4 100
4 200
4 300
4 200 | 800 |
Explicación
- 10 + 3 + 7
- Primero, realiza la tarea con fecha límite 1 ⇒ ganas 3
- Luego realiza la tarea con fecha límite 2 ⇒ ganas 7
- Finalmente realiza la tarea con fecha límite 4 ⇒ ganas 10
- 100 + 200 + 300 + 200 (solo realiza tareas con fecha límite 4)
- Realiza la tarea con beneficio de 100
- Realiza la tarea con beneficio de 200
- Realiza la tarea con beneficio de 300
- Realiza la tarea con beneficio de 200
Constraints
Time limit: 2 seconds
Memory limit: 512 MB
Output limit: 1 MB