13381번 - Jump 다국어

문제

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 e_i.

You can jump only right or up direction. That is, you can jump from a tile (x₁, y₁) to a tile (x₂, y₂) only if y₁=y₂ and x₁<x₂ (right direction) or x₁=x₂ and y₁<y₂ (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 x_i y_i e_i (0 <= x_i, y_i <= 100,000; 0 <= e_i <= 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.

제한

힌트