Uma empresa está a testar uma tecnologia de produção de antimatéria, utilizada como combustível numa nave espacial interplanetária. A antimatéria é produzida através de experiências especiais num reator.

São conhecidos $n$ tipos de experiências que produzem antimatéria. Ao realizar uma experiência do tipo $i$, são adicionados ao recipiente de saída do reator entre $l_i$ e $r_i$ gramas de antimatéria. Por razões de segurança, é proibido acumular mais de $a$ gramas de antimatéria no recipiente.

O custo de realizar uma experiência do tipo $i$ é $c_i$, e o valor de um grama da antimatéria produzida é $10^9$.

Se, após realizar as experiências, houver $t$ gramas de antimatéria no recipiente e o custo total das experiências no reator for $s$, o lucro é dado pela fórmula $(t\cdot 10^9-s)$. A empresa precisa de desenvolver uma estratégia para realizar experiências que maximize o lucro que se pode obter de forma garantida.

Em função dos resultados das experiências anteriores, a estratégia determina o tipo de experiência a realizar ou decide interromper a realização de experiências. Uma estratégia permite obter de forma garantida um lucro $x$ se, quaisquer que sejam os resultados das experiências, em primeiro lugar, o recipiente do reator contiver no máximo $a$ gramas de antimatéria e, em segundo lugar, o lucro for pelo menos $x$.

Por exemplo, suponha que existe apenas um tipo de experiência, que produz entre $4$ e $6$ gramas de antimatéria, custa $10$ e que a capacidade do recipiente é de $17$ gramas. Depois de realizar a experiência duas vezes, o recipiente pode conter entre $8$ e $12$ gramas de antimatéria. Se tiverem sido produzidos $12$ gramas, não se pode realizar mais nenhuma experiência, pois, se forem produzidos $6$ gramas, o recipiente poderá transbordar. Nos restantes casos, pode-se realizar a experiência uma terceira vez e obter entre $12$ e $17$ gramas de antimatéria. No pior caso, será necessário realizar a experiência três vezes, com um custo total de $30$, e o lucro será $(12\cdot 10^9-30)=11\,999\,999\,970$.

Escreva um programa que determine o lucro máximo $x$ que se pode obter de forma garantida.

Entrada

A primeira linha da entrada contém dois números inteiros: $n$, o número de tipos de experiências, e $a$, a quantidade máxima permitida de antimatéria no recipiente ($1\le n\le 100$, $1\le a\le 2\,000\,000$).

As $n$ linhas seguintes contêm três números inteiros $l_i$, $r_i$ e $c_i$: respetivamente, a quantidade mínima e máxima de antimatéria produzida por uma experiência do tipo $i$ e o custo dessa experiência ($1\le l_i\le r_i\le a$, $1\le c_i\le 100$).

Saída

A saída deve conter um único número inteiro: o lucro máximo $x$ que se pode obter de forma garantida.

Exemplos

Entrada 1

1 17
4 6 10

Saída 1

11999999970

Entrada 2

2 11
2 2 100
3 5 5

Saída 2

9999999890

Subtarefas