← 返回题目列表

AtCoder · utpc2021_e

E. 边界框

中文机器翻译题面 查看原题

配点 : 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