The Lazy Cow

On a hot summer day, Bessie the cow feels lazy. She wants to pick a starting point in her field so that she can reach as much grass as possible within a short walk.

The field has $N$ grass patches ($1 \le N \le 100\,000$). Patch $i$ holds $g_i$ units of grass ($1 \le g_i \le 10\,000$) at a distinct point $(x_i, y_i)$ ($0 \le x_i, y_i \le 1\,000\,000$). Bessie chooses one point in the field as her start (it may coincide with a patch or use non-integer coordinates). She wants the maximum total grass within Manhattan distance $K$ of that point ($1 \le K \le 2\,000\,000$).

Each step moves 1 unit north, south, east, or west. For example, $(0,0)$ to $(3,2)$ needs 5 steps. A step may be split: half a unit north plus half a unit east still counts as one step.

• Line 1: integers $N$ and $K$
• Next $N$ lines: $g_i$, $x_i$, $y_i$ for each patch

Print one integer: the maximum grass Bessie can reach within $K$ steps when she picks the best start.

Rotate coordinates to $(u,v)=(x+y,x-y)$. A Manhattan ball becomes a box with $|u-u_0|\le K$ and $|v-v_0|\le K$. Sort by $u$, slide a window of width at most $2K$, and within each window slide on $v$ the same way.