한 회사가 행성 간 우주선의 연료로 쓰이는 반물질을 생산하는 기술을 시험하고 있다. 반물질은 반응기에서 특별한 실험을 수행하여 얻는다.

반물질을 생산하는 실험에는 $n$가지 유형이 알려져 있다. 유형 $i$의 실험을 수행하면 반응기의 출력 용기에 $l_i$그램에서 $r_i$그램의 반물질이 추가된다. 안전상의 이유로 용기에 $a$그램을 초과하는 반물질을 모아 두는 것은 금지된다.

유형 $i$의 실험 비용은 $c_i$이고, 얻은 반물질 1그램의 가치는 $10^9$이다.

실험 후 용기에 반물질이 $t$그램 생겼고 반응기에서 수행한 실험의 총비용이 $s$라면, 이익은 $(t\cdot 10^9-s)$로 정의된다. 회사는 확실하게 얻을 수 있는 이익을 최대화하는 실험 전략을 개발해야 한다.

전략은 앞선 실험의 결과에 따라 다음에 어떤 유형의 실험을 수행할지, 또는 더 이상 실험하지 않을지를 결정한다. 어떤 실험 결과가 나오더라도 첫째로 반응기 용기의 반물질이 $a$그램 이하이고, 둘째로 이익이 $x$ 이상이라면, 그 전략은 이익 $x$를 확실하게 얻을 수 있다고 한다.

예를 들어, $4$그램에서 $6$그램의 반물질을 생산하는 한 가지 실험 유형만 가능하고, 그 실험 비용은 $10$이며, 용기의 용량은 $17$그램이라고 하자. 실험을 두 번 수행하면 용기에 반물질이 $8$그램에서 $12$그램 들어 있을 수 있다. $12$그램을 얻었다면 더 이상 실험할 수 없다. 다음 실험에서 $6$그램이 나오면 용기가 넘칠 수 있기 때문이다. 그 밖의 경우에는 세 번째 실험을 수행하여 $12$그램에서 $17$그램의 반물질을 얻을 수 있다. 최악의 경우 실험을 세 번 수행해야 하므로 총비용은 $30$이고 이익은 $(12\cdot 10^9-30)=11\,999\,999\,970$이다.

확실하게 얻을 수 있는 최대 이익 $x$를 구하는 프로그램을 작성하라.

입력

첫 번째 줄에는 실험 유형의 수 $n$과 용기에 허용되는 반물질의 최대량 $a$를 나타내는 두 정수가 주어진다 ($1\le n\le 100$, $1\le a\le 2\,000\,000$).

다음 $n$개의 줄에는 각각 세 정수 $l_i$, $r_i$, $c_i$가 주어진다. 각각 유형 $i$의 실험으로 얻는 반물질의 최소량, 최대량, 그리고 해당 실험의 비용을 나타낸다 ($1\le l_i\le r_i\le a$, $1\le c_i\le 100$).

출력

확실하게 얻을 수 있는 최대 이익 $x$를 나타내는 정수 하나를 출력하라.

예제

입력 1

1 17
4 6 10

출력 1

11999999970

입력 2

2 11
2 2 100
3 5 5

출력 2

9999999890

서브태스크