## Canada Day Contest 2021 - Starfall

View as PDF

Points: 15
Time limit: 2.0s
Memory limit: 256M

Author:
Problem type

A meteor shower is approaching the Monkey Empire. At the th second, a meteor will fall at 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 , but once it has been set, the tarp can only be moved by up to units in the and direction per second independently (You can move units in both directions at once). In addition, the tarp is aligned with the and 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 , the number of meteors, and , the tarp speed.

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

#### Output Specification

Output the minimum side length of the tarp.

#### 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 , so it cannot move. It must be big enough to cover both and 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 , the bottom left corner of the tarp is at . It moves 1 unit up and right by time . The top right corner now covers .

#### 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 to catch the first meteor, moves units up to catch the second meteor, then moves 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