GJ se ha introducido en el negocio de baratijas, comprando y vendiendo baratijas como adornos navideños vacunos. El sabe que venderá cada baratija que él pueda almacenar de un catalogo de ~N~ ~(1 \leq N \leq 1000)~ baratijas vacunas, y él puede comprar tantas de estas baratijas como su corazón desee. El tiene únicamente ~M~ ~(1 \leq M \leq 100,000)~ dinero para invertir, pero quiere maximizar su ganancia.

La Baratija de tipo ~i~ cuesta ~C_i~ ~(1 \leq C_i \leq 100,000)~ dinero para adquirir por unidad y produce ~R_i~ ~(1 \leq R_i \leq 100,000)~ de retorno por cada baratija vendida (una ganancia de ~R_i-C_i~). GJ puede mezclar y aparear las baratijas que él vende de cualquier manera que él desee. El no necesita gastar todo su dinero cuando compra baratijas.

¿Cuál es la cantidad más grande de ganancia total según la fórmula

ganancia = (dinero_inicial) – (los costos de todas las ventas) + (ganancia de todas las ventas)

que GJ puede tener al final del primer año? Se garantiza que este número será menor que ~1,000,000,000~.

Considere la situación cuando GJ tiene exactamente 3 tipos de baratijas y comienza con ~M=17~. A continuación están los costos y retornos para cada baratija:

       Baratija    Costo     Retorno
           #        C_i       R_i
           1         2         4
           2         5         6
           3         3         7

En este caso, GJ debería comprar ~5~ baratijas del tipo ~3~ por ~15~ dinero y ~1~ baratija de tipo ~1~ por ~2~ dinero, un total de ~17~ dinero. Su ganancia sería ~5 * (7-3) + 1 * (4-2) = 5*4 + 1*2 = 22~ dinero. El no puede hacer mejor que esto dado la estructura de costo y retorno.

Entrada

• Línea 1: Dos enteros separados por espacio: ~N~ y ~M~.
• Líneas 2:..N+1: la línea ~i+1~ contiene dos enteros separados por espacio: ~C_i~ y ~R_i~.

Salida

La ganancia máxima que GJ puede generar dados los costos y retornos.

Ejemplo de Entrada

3 17
2 4
5 6
3 7

Ejemplo de Salida

22