FJ se dedica a comprar y vender curiosidades, como adornos de árbol de Navidad en forma de vaca. Sabe que venderá cada artículo que consiga de un catálogo de $N$ ($1 \le N \le 100$) tipos de curiosidades de vacas, y puede comprar tantos de cada tipo como desee. Solo tiene $M$ ($1 \le M \le 100,000$) de dinero para invertir, pero quiere maximizar su beneficio (con una definición algo inusual) al final del primer año.

Cada artículo del tipo $i$ cuesta $C_i$ ($1 \le C_i \le 100,000$) y genera $R_i$ ($1 \le R_i \le 100,000$) de ingresos al venderse (beneficio $R_i-C_i$). FJ puede combinar los artículos que vende como quiera. No tiene que gastar todo su dinero al comprarlos.

¿Cuál es el máximo beneficio total ($profit = initial\_cash - all\_costs + all\_sales$) al terminar el primer año? Se garantiza que es menor que $1,000,000,000$.

Considera solo $3$ tipos de artículos y una cantidad inicial $M=17$. Los costes e ingresos de cada tipo son:

             Artículo     Coste     Ingreso
               #        C_i       R_i
               1         2         4
               2         5         6
               3         3         7

FJ debe comprar $5$ artículos del tipo $3$ por $15$ y $1$ más del tipo $1$ por $2$, un total de $17$. Su beneficio será $5 * (7-3) + 1 * (4-2) = 5*4 + 1*2 = 22$. Con estos costes e ingresos no puede hacerlo mejor.

Nota: el segundo caso de prueba es difícil, pero nuestra respuesta es correcta.

Entrada

• Línea 1: dos enteros separados por espacios: $N$ y $M$.

• Líneas $2..N+1$: la línea $i+1$ contiene dos enteros separados por espacios: $C_i$ y $R_i$.

Salida

• Línea 1: el máximo beneficio que FJ puede generar con los costes e ingresos dados.

Ejemplos

Entrada 1

3 17
2 4
5 6
3 7

Salida 1

22

Fuente del problema: problema tradicional, 2009.