配点 : 100 点
問題文
有 N 一个点。i 第 个点位于坐标 (x_i, y_i) ,其价值为 c_i 。
你的工作是N 点中恰好选择 K 个点。之后,定义变量如下。
- X_{\max} \coloneqq 所选点的 x 坐标最大值
- X_{\min} \coloneqq 所选点的 x 坐标最小值
- Y_{\max} \coloneqq 所选点的 y 坐标最大值
- Y_{\min} \coloneqq 所选点的 y 坐标最小值
- S \coloneqq 所选点的价值总和
在选择完点之后,你将获得作为奖励 (X_{\max} - X_{\min}) + (Y_{\max} - Y_{\min}) + S 日元可以获得。请求出最多可以获得多少日元的奖励。
制約
- 所有输入均为整数
- 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 \le N \le 1000 的数据集 给出 30 点。 如果您正确回答了所有满足
入力
输入是按以下格式从标准输入给出的。
N K x_1 y_1 c_1 \vdots x_N y_N c_N
出力
答案 请打印除以 1 行输出。
入力例1
3 2 1 3 1 3 1 1 3 3 2
出力例1
6
1 点和 2 点被选择时,奖励金额为 (3 - 1) + (3 - 1) + 2 = 6 在, 6 日元。由于无法达到更高的金额,因此6 就是答案。
入力例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