题目描述
地图上有 $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$
子任务：
| 子任务编号 | 特殊性质 | 分值 |
|---|---|---|
| $1$ | $N \le 20$ | $15$ |
| $2$ | $N \le 50$ | $10$ |
| $3$ | $N \le 500$ | $10$ |
| $4$ | $N \le 5000$ | $10$ |
| $5$ | $K \le 2$ | $10$ |
| $6$ | $K \le 5$ | $15$ |
| $7$ | $c_i = 1$ | $10$ |
| $8$ | 无 | $20$ |