题目描述

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 所能获得的最多单位牧草数

4 3
7 8 6
3 0 0
4 6 0
1 4 2

8