Prince


Submit solution

Points: 100 (partial)
Time limit: 1.0s
Java 8 2.0s
Python 2.0s
Memory limit: 64M
Java 8 128M
Python 128M

Author:
Problem type
Allowed languages
Ada, Assembly, Awk, BrainF***, C, C#, C++, Dart, Go, Java, JS, Kotlin, Lua, Pascal, Perl, Prolog, Python, Scala, Swift, VB

Prince ha decidido robar un banco para llevarse tanto dinero como sea posible. En el banco hay N (1 \le N \le 250) bolsas para guardar el dinero. Cada bolsa tiene un peso Wb (1 \le Wb \le 400) y una cantidad de billetes Cb (1 \le Cb \le 100). Sin embargo, Prince solo puede transportar en su carro un peso menor o igual a M (1 \le M \le 1000). Por esta razón Prince te ha pedido ayuda para resolver el siguiente problema: Dados el límite de peso como una restricción y una lista de bolsas con sus pesos y cantidades de billetes, calcule la mayor suma de billetes que Prince puede transportar.

Entrada

La primera línea de la entrada representa el número de robos planificados por Prince. Para cada robo se tiene la siguiente información:

  • Dos enteros separados por un espacio en blanco: N y M.
  • Las siguientes N líneas describen una bolsa con dos enteros separados por un espacio: Wb and Cb.

Salida

La salida contiene un entero que indica la mayor suma de billetes que Prince puede transportar al final de todos los robos.

Ejemplo de entrada

2
4 6
1 4
2 6
3 12
2 7
4 6
1 4
2 6
3 12
2 7

Ejemplo de salida

46

Comments


  • 1
    Marco_Escandon  commented on Dec. 28, 2023, 5:01 a.m.

    Para los que tienen cierta inquietud con el enunciado del problema, aquí tienen un problema espero les guste, es una mochila: http://www.usaco.org/index.php?page=viewproblem2&cpid=1045


  • 3
    Osnielfc_07  commented on March 28, 2022, 5:41 p.m.

    El problema no te lo especifica pero con una mochila simple, bien hecha para cada caso , el problema entra en tiempo , por lo general si no te dan el dato es porque este no es muy grande.


    • 0
      JAMachado  commented on March 28, 2022, 6:44 p.m.

      Ok, gracias


  • 0
    JAMachado  commented on March 28, 2022, 2:29 p.m.

    Una pregunta. Alguien podria decirme cual es el max de casos de prueba?


  • 0
    Iris  commented on July 27, 2021, 8:46 p.m.

    Alguien puede explicarme en el ejemplo que significan los dos números de cada fila?


    • 1
      aniervs  commented on July 27, 2021, 8:58 p.m.

      Cada línea contiene la información de una bolsa: su peso y la cantidad de billetes que tiene.


  • 0
    josue  commented on May 4, 2020, 10:54 a.m.

    alguien me puede explicar que me piden en este problema


    • 0
      aniervs  commented on May 6, 2020, 5:16 p.m.

      Te piden buscar la suma de la máxima cantidad de billetes en cada robo. En el ejemplo, en cada robo lo Máximo que se puede obtener son 23 billetes, por lo que en total son 46 billetes.


  • 4
    elpro204  commented on Feb. 6, 2020, 4:59 p.m.

    por qué debo ayudar a un ladron


    • 4
      Maite  commented on Oct. 29, 2021, 5:15 p.m.

      x q te lo dice el problema?


  • 0
    Sniper  commented on Feb. 20, 2019, 4:01 p.m. edited

    deja


  • 0
    Sniper  commented on Feb. 20, 2019, 3:59 p.m. edit 2

    M donde esta?


    • 0
      aniervs  commented on Feb. 21, 2019, 11:47 p.m.

      Lee bien, inicialmente te dan la cantidad de casos a procesar, y en cada caso te dan N y M.