A meteor shower is approaching the Monkey Empire. At the ~t_i~th second, a meteor will fall at ~(x_i,y_i)~ and destroy the planet. Luckily, the monkeys have a square tarp that they can use to catch the meteors. They can set up the tarp at any location initially at time ~0~, but once it has been set, the tarp can only be moved by up to ~K~ units in the ~\pm x~ and ~\pm y~ direction per second independently (You can move ~K~ units in both directions at once). In addition, the tarp is aligned with the ~x~ and ~y~ axis and cannot be rotated. What is the minimum tarp side length required to catch all meteors?

Assume the meteors have insignificant size.

Input Specification

The first line contains an integer ~n~, the number of meteors, and ~K~, the tarp speed.

The next ~n~ lines contain three integers each: ~t_i~, ~x_i~, and ~y_i~, the time and location of the ~i~th meteor strike. The input is given in order of nondecreasing time.

Output Specification

Output the minimum side length of the tarp.

Constraints

~1 \le n \le 400\,000~

~0 \le K \le 400\,000~

~0 \le t_i, x_i, y_i \le 10^9~

Sample Input 1

2 0
1 0 0
2 0 3

Sample Output 1

3

Explanation For Sample 1

The tarp has a speed of ~0~, so it cannot move. It must be big enough to cover both ~(0,0)~ and ~(0,3)~ at the same time.

Sample Input 2

2 1
1 0 0
2 3 3

Sample Output 2

2

Explanation For Sample 2

At time ~1~, the bottom left corner of the tarp is at ~(0,0)~. It moves 1 unit up and right by time ~2~. The top right corner now covers ~(3,3)~.

Sample Input 3

3 1
1 100 100
3 100 105
103 0 5

Sample Output 3

3

Explanation For Sample 3

The tarp starts with the bottom left corner at ~(100,100)~ to catch the first meteor, moves ~2~ units up to catch the second meteor, then moves ~100~ units left to catch the third meteor.

Sample Input 4

3 1000
1 0 0
1 5 1
2 100 100

Sample Output 4

5

Sample Input 5

3 100
0 1 3
1 4 2
5 0 0

Sample Output 5

0