Speed Ups

Speed Ups라는 비디오 게임에서 한 명의 플레이어가 경주를 한다. 목표는 경주를 가능한 한 빨리 끝내는 것이다. 평소 속도는 1미터/초이다. 여러 미터 지점에서 속도 향상을 고를 수 있다. 각 속도 향상은 정수로 이루어진 순서쌍 $(x, m, d)$로 나타낸다. 경주를 시작하고 정확히 $x$미터 뒤에 사용할 수 있으며, $d$초 동안 속도가 $m$미터/초가 된다. 속도 향상을 사용하는 동안에는 다른 속도 향상을 사용할 수 없다. 따라서 하나를 고르면 더 나은 다른 속도 향상이 있는 지점을 지나칠 수 있다.

예를 들어 100미터 경주에 $(10, 2, 5)$와 $(15, 3, 20)$ 두 속도 향상이 있다고 하자. 처음 10미터는 10초에 달린다. 첫 번째 속도 향상을 쓰면 5초 동안 2미터/초로 달려 15초에 20미터 지점에 도달한다. 이는 15미터에 있는 두 번째 속도 향상을 지난 위치이므로 그것은 쓸 수 없다. 이 경우 완주 시간은 $10 + 5 + 80 = 95$초이다. 첫 번째를 건너뛰고 15미터의 두 번째 속도 향상을 쓰면, 20초 동안 3미터/초로 달려 35초에 75미터 지점에 도달하고 60초에 완주한다. 이 예에서는 이것이 가장 빠른 완주 시간이다.

첫 줄에 정수 $n$ ($1 \le n \le 1000$)과 $L$ ($1 \le L \le 10^{9}$)이 주어진다. $n$은 사용할 수 있는 속도 향상의 개수이고, $L$은 경주 길이(미터)이다.

다음 $n$개 줄에는 각각 정수 $x$ ($1 \le x \le L - 1$), $m$ ($2 \le m \le 100$), $d$ ($1 \le d \le 10^{6}$)가 주어진다. 출발점에서 $x$미터 떨어진 곳에 속도 향상이 있으며, 이를 쓰면 $d$초 동안 속도가 $m$미터/초가 된다는 뜻이다.

유의할 점은 다음과 같다.

• 같은 위치에 속도 향상이 여러 개 있을 수 있지만, 그중 하나만 고를 수 있다.
• 속도 향상을 고르면 완료되거나 경주가 끝날 때까지 계속 사용해야 한다.
• 현재 속도 향상이 완전히 끝나기 전에는 다른 속도 향상을 쓸 수 없다.
• 어떤 속도 향상으로 출발점에서 거리 $y$에 도달했을 때, 정확히 $y$ 지점에 새 속도 향상이 있다면 그것을 고를 수 있다.

가장 빠른 완주 시간을 초 단위로 한 줄에 출력한다. 절대 오차나 상대 오차가 $10^{-6}$ 이내이면 정답으로 인정한다.

두 번째 예에서는 세 번째 속도 향상을 고르면 두 번째를 쓸 수 없게 되므로, 첫 번째 속도 향상을 고르는 편이 낫다. 25미터 지점에서 첫 번째를 고르면 25초 동안 3미터/초로 달려 50초에 100미터 지점에 도달한다. 그다음 두 번째를 고르면 400초 동안 2미터/초로 달려 450초에 900미터 지점에 도달한다. 남은 100미터는 1미터/초로 100초 달린다.

마지막 예에서는 7초 뒤에 고른 속도 향상이 200초 동안 유지되지만, 그 전에 경주가 끝난다. 남은 43미터를 4미터/초로 달리는 데 10.75초가 걸린다.