题目描述

平面上有 $n$ 处候选景点，第 $i$ 处景点的坐标为 $(x_i,y_i)$，价值为 $c_i$。你需要从中选出恰好 $k$ 处景点，获得它们的价值总和，以及由取景范围决定的额外奖励。

设所选景点的横坐标范围为 $[X_{\min},X_{\max}]$，纵坐标范围为 $[Y_{\min},Y_{\max}]$。总收益为

$$\sum_{i\text{ 被选中}}c_i+(X_{\max}-X_{\min})+(Y_{\max}-Y_{\min}).$$

求总收益的最大值。

编号不同的景点视为不同景点，即使它们的坐标相同也可以分别选择。只选择一处景点时，两个方向的坐标跨度都为 $0$，没有额外奖励。

输入格式

第一行包含两个整数 $n,k$，表示候选景点数和需要选择的景点数。

接下来 $n$ 行，第 $i$ 行包含三个整数 $x_i,y_i,c_i$，表示第 $i$ 处景点的坐标和价值。

输出格式

输出一行一个整数，表示可以获得的最大总收益。

样例输入 1

4 2
1 1 5
5 1 1
1 5 1
5 5 4

样例输出 1

17

样例 1 解释

选择第 $1$、$4$ 处景点，价值总和为 $9$，横、纵两个方向的跨度均为 $4$，总收益为 $9+4+4=17$，这是最大值。

样例输入 2

3 1
2 8 6
2 8 9
9 2 7

样例输出 2

9

样例 2 解释

只需选择一处景点，不会获得额外奖励。选择价值最高的第 $2$ 处景点，可获得总收益 $9$。

数据范围与子任务

对于所有测试数据，保证$1\le k\le n\le2\times10^5$，$1\le x_i,y_i,c_i\le10^9$。

每个子任务内的正式测试全部通过，才获得该子任务的分数。

子任务编号	分值	额外限制
1	20	$n\le18$
2		$n\le200$
3		$k\le4$
4	40	无额外限制