Horario de Ordeño


Submit solution

Points: 100 (partial)
Time limit: 1.0s
Memory limit: 64M

Author:
Problem type
Allowed languages
Ada, BrainF***, C, C#, C++, Dart, Go, Java, JS, Kotlin, Prolog, Swift, VB

El Granjero Juan tiene N vacas que necesitan ser ordeñadas (1 \leq N \leq 10 000). Ordeñar cada vaca toma únicamente un minuto.

Siendo animales impacientes, algunas vacas se rehúsan a ser ordeñadas si el Granjero Juan las hace esperar mucho para él ordeñarlas. Más específicamente, la vaca i produce g_i galones de leche (1 \leq g_i \leq 1000) únicamente si es ordeñada ante de un límite de tiempo d_i (0 \leq d_i \leq 10 000). El tiempo comienza en 0, por lo tanto a lo más x vacas en total pueden ser ordeñadas antes de un límite en el tiempo t = x.

Por favor, ayude al Granjero Juan a determinar la máxima cantidad de leche que él puede obtener si él ordeña a las vacas óptimamente.

Entrada

• Línea 1: El valor de N.

• Líneas 2...1+N: La línea i+1 contiene los enteros g_i y d_i.

Ejemplo de Entrada

4
10 3
7 5
8 1
2 1

Detalles de la Entrada

Hay 4 vacas. La primera produce 10 galones de leche si es ordeñada hasta en el tiempo 3, y así sucesivamente.

Salida

• Línea 1: El número máximo de galones de leche que el Granjero Juan puede obtener.

Ejemplo de Salida

25

Detalles de la Salida

El Granjero Juan ordeña primero a la vaca 3, descartando a la vaca 4 pues no puede ser ordeñada en su límite de tiempo debido al conflicto con la vaca 3. El Granjero Juan después ordeña a las vacas 1 y 2.


Comments

There are no comments at the moment.