Algoritmos y Estructuras de Datos

Mochila fraccionaria

Dado que tienes n artículos con sus pesos y valores, deseas colocar esos artículos en una mochila de capacidad W para obtener el mayor valor total posible. Se te permite tomar una fracción (parte) de un artículo; en ese caso, el precio cambia proporcionalmente a la fracción que tomes.

¿Cuál sería el valor total máximo que puede llevar la mochila?

Entrada

La primera línea de la entrada contiene dos enteros n (1 ≤ n ≤ ), que representan el número de artículos, y W (1 ≤ W ≤ ), la capacidad de tu mochila.

Las siguientes n líneas contienen pares de enteros separados por espacio (1 ≤ , ≤ ) que indican el peso y el valor de cada artículo.

Salida

El programa debe imprimir el valor total máximo que puede llevar la mochila.

Ejemplos

Entrada

Salida

3 50
10 60
20 100
30 120

240

4 60
40 280
10 100
20 120
24 120

440

Explicación

  1. 60 + 100 + (2/3)120 = 240

  2. 280 + 100 + (10/20)120 = 440

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