题目描述

地图上有$N$座防御塔，第$i$座塔在位置 $(x_i,y_i)$，有价值$c_i$，偷一座塔需要一秒钟的时间。

你的队友只能牵制监管者$K$秒，故你只能偷$K$座塔。

令：
·$X_{max}$表示你偷的$K$座塔中，$x$坐标的最大值。

·$X_{min}$表示你偷的$K$座塔中，$x$坐标的最小值。

·$Y_{max}$表示你偷的$K$座塔中，$y$坐标的最大值。

·$Y_{min}$表示你偷的$K$座塔中，$y$坐标的最小值。

·$S$表示你偷的$K$座塔中，价值$c$的和。

你需要选择 $K$ 座塔，最大化$(X_{max} -X_{min})+(Y_{max} -Y_{min}) + S$

输入格式

第一行两个整数$N,K$。

接下来$N$行，其中第$i$行有三个整数，$x_i, y_i,c_i$，表示第$i$座塔的信息。

输出格式

输出一行一个整数表示答案。

样例1

输入#1

3 2  
1 3 1
3 1 1  
3 3 2  

输出#1

6

样例解释

选择防御塔 $1,2$ 即可。

样例#2

输入

12 5
79 29 4
47 96 11
31 100 13
89 67 13
28 45 9
66 70 12
18 12 9
21 57 14
67 17 6
91 12 9
79 11 8
67 50 6 

输出

220

数据范围与约定

对于所有数据，有：

·$1≤K≤N≤2*10^5$

·$1≤x_i,y_i≤10^9$

·$1≤c_i≤10^9$

子任务