Description

A new type of laser bomb can destroy all targets inside a square with side length $m$. There are $n$ targets on the map. Integers $x_i$ and $y_i$ denote the position of a target on the map, and each target has a value $v_i$. The bomb is aimed via satellite, but it has a drawback: the blast square, i.e., the square of side length $m$, must have its sides parallel to the x-axis and y-axis. If a target lies on the boundary of the blast square, it will not be destroyed.

Your task is to compute the maximum total value of targets that a single bomb can destroy.

Multiple targets may be located at the same position.

Input Format

The first line contains integers $n$ and $m$.

Each of the next $n$ lines contains three integers $x, y, v$, denoting a target’s coordinates and its value.

Output Format

Output a single positive integer, the maximum total value of targets that can be destroyed by one bomb (the result does not exceed 32767).

2 1
0 0 1
1 1 1

1

Hint

• Constraints
  • For $100\%$ of the testdata, it is guaranteed that $1 \le n \le 10^4$, $0 \le x_i , y_i \le 5\times 10^3$, $1 \le m \le 5\times 10^3$, $1 \le v_i < 100$.

Translated by ChatGPT 5