解题思路

设选出的 $M$ 件装备三项属性和分别为

$X=\sum x_j,\ Y=\sum y_j,\ Z=\sum z_j$

要求最大化

$|X|+|Y|+|Z|$

P4637.第1题-装备选配

1000ms

Difficulty: 3

所属公司 : 小米

算法与标签>贪心算法

在某款角色扮演游戏中，玩家的角色拥有三项核心属性:力量、敏捷和智力。你的仓库中目前存储了 $N$ 件装备，每一件装备都拥有这三项属性的数值。第 $i$ 件装备的力量值为 $x_i$ ，敏捷值为 $y_i$ ，智力值为 $z_i$ 。需要注意的是，这些数值可能为负数

为了应对即将到来的高难度副本，你需要从这 $N$ 件装备中恰好挑选出 $M$ 件进行装备。装备穿戴后，角色的最终属性值为所选 $M$ 件装备对应属性值的代数和，即

最终力量 $X=\sum x_j$ ，最终敏捷 $Y=\sum Y_j$ ，最终智力 $Z=\sum Z_j$

为了追求极致的战斗风格，角色强度评分为三项最终属性值的绝对值之和，即 $|X|+|Y|+|Z|$ 。请你计算一下，如何从 $N$ 件装备中挑选M件，才能使得角色的强度评分最大?

输入包含 $N+1$ 行。

第一行包含两个整数 $N$ 和 $M$ ，分别表示仓库中装备的总数和需要挑选的装备数量

接下来的 $N$ 行，每行包含三个整数 $x_i,y_i,z_i$ ，分别表示第 $i$ 件装备的力量、敏捷和智力属性值。 $1≤M≤N≤100000,-10^9≤x_i,y_i,Z_i≤10^9$ 。

输出一行，一个整数，表示能够达到的最大强度评分。

输入

输出

说明

在这个例子中，我们可以选择第 $1$ 、第 $3$ 和第 $5$ 件装备。各项属性的总和如下:

此时的强度评分为 $|21|+1-24|+19|=21+24+9=54$ 。

可以证明，没有其他方案能获得比 $54$ 更高的评分。

输入

预期输出（选填）