Una empresa está probando una tecnología para producir antimateria, que se utiliza como combustible en una nave espacial interplanetaria. La antimateria se obtiene mediante experimentos especiales en un reactor.

Se conocen $n$ tipos de experimentos que producen antimateria. Al realizar un experimento del tipo $i$, se añaden entre $l_i$ y $r_i$ gramos de antimateria al contenedor de salida del reactor. Por motivos de seguridad, está prohibido acumular más de $a$ gramos de antimateria en el contenedor.

El coste de realizar un experimento del tipo $i$ es $c_i$, y el valor de un gramo de la antimateria obtenida es $10^9$.

Si después de los experimentos hay $t$ gramos de antimateria en el contenedor y el coste total de los experimentos en el reactor es $s$, el beneficio se calcula mediante la fórmula $(t\cdot10^9-s)$. La empresa necesita desarrollar una estrategia para realizar experimentos que maximice el beneficio que se puede obtener con garantía.

En función de los resultados de los experimentos anteriores, la estrategia determina qué tipo de experimento debe realizarse o decide dejar de realizar experimentos. Una estrategia permite obtener con garantía un beneficio $x$ si, para cualquier resultado de los experimentos, en primer lugar, el contenedor del reactor contiene como máximo $a$ gramos de antimateria y, en segundo lugar, el beneficio es al menos $x$.

Por ejemplo, supongamos que solo hay un tipo de experimento, que produce entre $4$ y $6$ gramos de antimateria, cuesta $10$ y el contenedor tiene una capacidad de $17$ gramos. Después de realizar el experimento dos veces, puede haber entre $8$ y $12$ gramos de antimateria en el contenedor. Si se obtienen $12$ gramos, ya no se puede realizar otro experimento, pues si se producen $6$ gramos el contenedor podría desbordarse. En los demás casos se puede realizar el experimento una tercera vez y obtener entre $12$ y $17$ gramos de antimateria. En el peor caso habrá que realizar el experimento tres veces, con un coste total de $30$, y el beneficio será $(12\cdot10^9-30)=11\,999\,999\,970$.

Escribe un programa que determine el máximo beneficio $x$ que se puede obtener con garantía.

Entrada

La primera línea contiene dos enteros: $n$, el número de tipos de experimentos, y $a$, la cantidad máxima permitida de antimateria en el contenedor ($1\le n\le100$, $1\le a\le2\,000\,000$).

Cada una de las siguientes $n$ líneas contiene tres enteros $l_i$, $r_i$ y $c_i$: respectivamente, las cantidades mínima y máxima de antimateria obtenidas en un experimento del tipo $i$, y el coste de dicho experimento ($1\le l_i\le r_i\le a$, $1\le c_i\le100$).

Salida

La salida debe contener un entero: el máximo beneficio $x$ que se puede obtener con garantía.

Ejemplos

Entrada 1

1 17
4 6 10

Salida 1

11999999970

Entrada 2

2 11
2 2 100
3 5 5

Salida 2

9999999890

Subtareas