P4876 [USACO14MAR] The Lazy Cow G

Bessie 的田里有 $n$（$1\le n \le 10^5$）块草地，每块草地的坐标是 $(x_i,y_i)$（$0\le x_i,y_i\le 10^6$），上面长着 $gi$（$1\le g_i\le 10^4$）个单位的牧草。 Bessie 可以向东南西北方向走，一次走一步（一个单位长度）。如她从 $(0,0)$ 走到 $(3,2)$ 需要 $5$ 步。她最多可以一次走 $k$（$\le k \le 2\times 10^6$）步。 现在她想找一个位置，使她从该位置出发可以得到最多单位的牧草（她可以走多次，但每次都从该位置出发）。

第一行两个整数 $n$ 和 $k$。 第 $2$ 到 $n+1$ 行，每行三个整数 $g_i,x_i,y_i$。

一行一个整数，表示 Bessie 所能获得的最多单位牧草数

INPUT DETAILS: Bessie is willing to take at most 3 steps from her initial position. There are 4 patches of grass. The first contains 7 units of grass and is located at position $(8,6)$, and so on. OUTPUT DETAILS: By locating herself at $(3,0)$, the grass at positions $(0,0)$, $(6,0)$, and $(4,2)$ is all within $K$ units of distance.