It's a hot summer day, and Bessie the cow is feeling quite lazy. She wants to locate herself at a position in her field so that she can reach as much delicious grass as possible within only a short distance. There are $N$ patches of grass $(1\le N\le 100,000)$ in Bessie's field. The $i$-th such patch contains $g_i$ units of grass $(1\le g_i\le 10,000)$ and is located at a distinct point $(x_i, y_i)$ in the field $(0\le x_i, y_i\le 1,000,000)$. Bessie would like to choose a point in the field as her initial location (possibly the same point as a patch of grass, and possibly even a point with non-integer coordinates) so that a maximum amount of grass is within a distance of $K$ steps from this location $(1\le K\le 2,000,000)$. When Bessie takes a step, she moves $1$ unit north, south, east, or west of her current position. For example, to move from $(0,0)$ to $(3,2)$, this requires $5$ total steps. Bessie does not need to take integer-sized steps -- for example, $1$ total step could be divided up as half a unit north and half a unit east. Please help Bessie determine the maximum amount of grass she can reach, if she chooses the best possible initial location.

* Line $1$: The integers $N$ and $K$. * Lines $2\dots 1+N$: Line $i+1$ describes the $i$-th patch of grass using $3$ integers: $g_i$, $x_i$, $y_i$.

* Line $1$: The maximum amount of grass Bessie can reach within $K$ steps, if she locates herself at the best possible initial position.

By locating herself at $(3,0)$, the grass at positions $(0,0)$, $(6,0)$, and $(4,2)$ is all within $K$ units of distance.

USACO 2014 March Contest, Gold