Brazalete de Dijes.


Submit solution

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

Author:
Problem type
Allowed languages
C, C++, Java, Pascal, Python, VB

Bessie ha ido a la joyería del centro comercial y ha visto un brazalete de dijes. Por supuesto, ella quisiera llenarlo con los mejores dijes posibles de N (1 \leq N \leq 3,402) dijes disponibles. Cada dije i tiene un peso W_i (1 \leq W_i \leq 400) y una factor de 'deseabilidad' D_i (1 \leq D_i \leq 100). Bessie puede únicamente soporta un brazalete de dijes cuyo peso sea menor que M (1 \leq M \leq 12,880).

Dado el peso límite como una restricción y una lista de los dijes con sus pesos y factores de deseabilidad, deduzca la mayor suma posible de deseabilidades.

Entrada

  • Línea 1: Dos enteros separados por espacio: N y M.
  • Líneas 2..N+1: La línea i+1 describe el dije i con dos enteros separados por espacio: W_i y D_i.

Ejemplo de Entrada

4 6
1 4
2 6
3 12
2 7

Detalles de la Entrada

Cuatro dijes potenciales, peso máximo 6

Salida

  • Línea 1: Un solo entero que es la suma más grande de deseabilidades de dijes que puede ser obtenida dadas las restricciones de peso

Ejemplo de Salida

23

Detalles de la Salida

Sin el segundo dije posible, el valor 4+12+7=23 es el valor más alto con un peso 1+2+3<=6


Comments


  • 1
    Brayan080808  commented on Aug. 8, 2022, 2:50 a.m.

    Alguien me ayudar con esto, se que es el problema de la mochila que lo e echo 100 veces pero no logro que entre en tiempo