점프

2차원 평면에 타일 $N$개가 놓여 있다. $i$번 타일의 좌표는 $(x_i, y_i)$이고, 그 위에는 점프 에너지를 $e_i$만큼 채워 주는 에너지 통이 하나 있다.

점프는 오른쪽 또는 위쪽으로만 한다. 타일 $(x_1, y_1)$에서 타일 $(x_2, y_2)$로 점프하려면 $y_1 = y_2$이면서 $x_1 < x_2$이거나(오른쪽), $x_1 = x_2$이면서 $y_1 < y_2$여야 한다(위쪽). 두 타일이 서로 붙어 있을 필요는 없고, 같은 행이나 같은 열에서 그 방향에 있는 타일이면 어디로든 점프할 수 있다. 타일이 없는 곳으로는 점프하지 못한다.

점프를 한 번 할 때마다 에너지를 $B$만큼 쓴다. 에너지가 $B$보다 적으면 점프할 수 없다. 새 타일에 도착하면 곧바로 그 타일의 에너지 통을 얻어 에너지가 $e_i$만큼 늘어난다.

출발 지점은 $1$번 타일이고, 출발할 때 에너지는 $e_1$이다. $1$번 타일에서 $N$번 타일까지 점프해서 이동하되, $N$번 타일에 도착했을 때 남는 에너지를 최대로 만들어야 한다.

$N$번 타일에 도착했을 때 가질 수 있는 최대 에너지를 구하는 프로그램을 작성하시오.

첫째 줄에 테스트 케이스의 개수 $T$가 주어진다. ($1 \le T \le 10$)

각 테스트 케이스의 첫째 줄에는 두 정수 $N$과 $B$가 주어진다. ($2 \le N \le 300000$, $1 \le B \le 1000$)

이어지는 $N$개 줄에는 $1$번 타일부터 $N$번 타일까지의 정보가 순서대로 주어진다. 각 줄에는 세 정수 $x_i$, $y_i$, $e_i$가 주어진다. ($0 \le x_i, y_i \le 100000$, $0 \le e_i \le 1000$)

좌표가 같은 타일은 없다. 에너지 규칙을 지키면서 $1$번 타일에서 $N$번 타일까지 갈 수 있는 점프 순서가 적어도 하나 존재한다.

각 테스트 케이스마다 $N$번 타일에 도착했을 때 가질 수 있는 최대 에너지를 한 줄에 하나씩 출력한다.