题目描述

地图上有 $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

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

样例输出 #2

220

样例输入/输出 #3~6

见下发文件。

数据范围与约定

对于所有数据，有：

• $1 \le K \le N \le 2 \times 10^5$
• $1 \le x_i,y_i \le 10^9$
• $1 \le c_i \le 10^9$

子任务：