Salchichas (3) P42697

Statement

—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\le 5$ y $T \le 10000$ .

TestB: Entradas con $N\le 100$ y $T \le 10000$ .

Public test cases

Input

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

Output

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

Information

Author: Omer Giménez
Language: Spanish
Official solutions: C++
User solutions: C++