Bessie’s Grass Feast

Bessie the cow is having a hot summer day and wants to position herself so that she can reach as much delicious grass as possible within a short Manhattan distance. In her field there are N patches of grass. The ith patch is located at a distinct point (x_i, y_i) and contains g_i units of grass.

Bessie can choose any starting position (which can even have non-integer coordinates) and when she takes a step, she moves 1 unit north, south, east, or west. In other words, the Manhattan distance between two points (x₁, y₁) and (x₂, y₂) is defined as:

$|x_1-x_2|+|y_1-y_2|$

A patch is considered reachable if its Manhattan distance from Bessie's starting position is at most K. Equivalently, by applying the change of variables \(u=x+y\) and \(v=x-y\), the reachable region becomes a fixed axis-aligned rectangle:

$u_0\le u\le u_0+2K$ and $v_0\le v\le v_0+2K$

Your task is to determine the maximum total amount of grass Bessie can reach by choosing the best possible initial position.

inputFormat

The first line contains two integers N and K (1 <= N <= 100,000, 1 <= K <= 2,000,000), where N is the number of grass patches and K is the maximum Manhattan distance Bessie can cover.

Each of the following N lines contains three integers: xi, yi (0 <= xi, yi <= 1,000,000) and gi (1 <= gi <= 10,000), representing the coordinates and the units of grass in the ith patch. All patches are at distinct locations.

outputFormat

Output a single integer representing the maximum total units of grass that Bessie can access from an optimally chosen starting position.

sample

3 2
0 0 5
2 2 7
4 0 3

12