题目描述

这是一个炎热的夏日，奶牛贝西感到很懒。她想要将自己定位在自己领域的某个位置，这样她就可以旧能多地接触到在很短的距离内旧能地种植美味的草。

贝西的田地里有$\red{N}$片草地（$\red{1<=N<=100000}$)。 第$\red{i}$个此类斑块包含$\red{g_i}$单位的草（$\red{1<=g_i<=10000}$)

并且位于字段（$\red{0<=x\u i，}$$\red{y_i<=1000000}$)。

贝西想在球场上选一个位置 作为她的初始位置（可能与一片草地相同， 甚至可能是一个具有非整数坐标的点） 最大草量在此距离$\red{K}$步以内位置（$\red{1≤}$$\red{K≤}$$\red{2000000}$)。

当贝西迈出一步时，她会将$\red{1}$个单元从她目前的职位。

例如，要（$\red{0,0}$)移动到（$\red{3,2}$)，此总共需要$\red{5}$个步骤。贝西不需要取整数大小步骤——例如，一个总步骤可以划分为半个单元北面和东面半个单位。

如果需要，请帮助贝西确定她能够到的最大草量她选择了可能的最佳初始位置。

输入格式

第 $\red{1 }$行：整数 $\red{N }$和 $\red{K}$。

第 $\red{2..1+N }$行：第 $\red{i+1 }$行使用 $\red{3 }$个整数描述第 $\red{i }$块草地：$\red{g_i}$、$\red{x_i}$、$\red{y_i.}$

输出格式

第 $\red{1 }$行：$\red{Bessie }$在 $\red{K }$步内可以达到的最大草量。

样例

输入样例

4 
37 
8 
63
0 
04 
6
01 
4 
2

输出样例

80

提示

输入详细信息：贝西愿意从初始位置最多走$\red{3}$步。有$\red{4}$片草地。第一个包含$\red{7}$个单位的草，位于位置（$\red{8,6}$)，以此类推。

细节：通过将自己定位在（$\red{3,0}$） ，位置（$\red{0,0}$）、（$\red{6,0}$）（$\red{4,2}$）处的草都在$\red{K}$个距离单 位内。