Salchichas (3) P42697


Statement
 

pdf   zip

html

—Muy bien, muy bien— comenta el carnicero. —Sin duda, el problema Salchichas (2) no es más difícil que el problema Salchichas (1). Pero esta vez tengo un problema bastante mas difícil entre manos. Cada cliente me ha dado una lista con varias cantidades distintas de salchichas, y para cada cantidad, los euros que me pagará en caso que pueda satisfacer su pedido. ¿Podrías ayudarme a maximizar los beneficios que obtenga por vender mis T salchichas? (No es necesario satisfacer a todos los clientes: un cliente insatisfecho recibirá 0 salchichas y pagará 0 euros).

Entrada

Cada entrada contiene una cantidad arbitraria de casos, no mayor que 5. La primera línea contiene el número N de clientes y la cantidad total T de salchichas. Las siguientes N líneas contienen las listas con los pedidos de los clientes: para cada cliente, una cantidad arbitraria (no mayor de 10) de pares c e, con una cantidad c de salchichas y la cantidad e de euros que el cliente pagará si recibe exactamente c salchichas. Los valores c y e se dan separados por un espacio, mientras que pares consecutivos se separan por dos espacios.

Salida

Para cada caso de pruebas escribe una línea con la máxima cantidad de euros que el carnicero puede conseguir vendiendo T (o menos) salchichas.

Puntuación

  • TestA:   Entradas con N≤ 5 y T ≤ 10000.  40 Puntos 
  • TestB:   Entradas con N≤ 100 y T ≤ 10000.  60 Puntos 
Public test cases

  • Input

    3 100
10 10  25 15  20 17
100 30  40 25
10 7  15 8  35 10

    Output

    52

  • Input

    3 70
10 10  25 15  20 17
100 30  40 25
10 7  15 8  35 10
1 100
99 20  100 25  101 30

    Output

    49
25

  • Input

    3 200
10 10  25 15  20 17
100 30  40 25
10 7  15 8  35 10

    Output

    57
    • Information
    Author
    Omer Giménez
    Language
    Spanish
    Official solutions
    C++
    User solutions
    C++