시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
2 초 512 MB 12 4 4 57.143%

문제

In ACM city, there are N tiles staying in two-dimensional Cartesian coordinate (xi, yi). Each tile has a power bottle for boosting the jumping energy ei.

You can jump only right or up direction. That is, you can jump from a tile (x1, y1) to a tile (x2, y2) only if y1=y2 and x1<x2 (right direction) or x1=x2 and y1<y2 (up direction).

Each time you jump, you have to loss your jumping energy B. You could not jump if your jumping energy is less than B and when you reach the new tile, you will get the power bottle for boosting your jumping energy ei immediately.

You initially stay in the first tile and you initially have energy e1. Your mission is to jump from the first-tile to the N-th tile (the last tile) and also get the maximum energy. In this task, you can jump only from a tile to a tile. You cannot jump outside the tile.

Your task

Write a program to find the maximum energy to jump from the first tile to the N-th tile.

입력

The first line of the input contains an integer T, the number of test cases (1 <= T <= 10). Then T test cases follow in the format described below.

The first line of each test case contains two positive integers N and B. (2 <= N <= 300,000; 1 <= B <= 1,000)

The next N lines describe each tile from the first tile to the N-th tile. Each line contains three integers xi yi ei (0 <= xi, yi <= 100,000; 0 <= ei <= 1,000)

Guarantee that no two tiles stay in the same coordinate and there is a way that you can jump from the first tile to the N-th tile.

출력

The output contains T lines show the maximum energy to jump from the first tile to the N-th tile.

예제 입력

2
6 20
10 10 20
15 10 20
10 15 15
15 20 20
20 15 200
20 20 20
6 20
10 10 20
15 10 20
10 15 20
15 20 20
20 15 200
20 20 20

예제 출력

20
200

힌트