Patisserie ABC

题目描述

Takahashi 成为了一名甜点师，并为庆祝 AtCoder Beginner Contest 100 开了家名为 La Confiserie d'ABC 的店。 这家店出售 $N$ 种蛋糕。
每种蛋糕有三个参数：“美丽度”（beauty）、“美味度”（tastiness）和“人气”（popularity）。第 $i$ 种蛋糕的美丽度为 $x_i$，美味度为 $y_i$，人气为 $z_i$。
这些数值可能为零或负数。 Ringo 决定在这里吃 $M$ 块蛋糕。他将按如下方式选择蛋糕集合：

不吃两块或更多相同种类的蛋糕。 在上述条件下，选择蛋糕集合以最大化（总美丽度的绝对值）+（总美味度的绝对值）+（总人气的绝对值）。

求 Ringo 选择的蛋糕集合能获得的（总美丽度的绝对值）+（总美味度的绝对值）+（总人气的绝对值）的最大可能值。

输入格式

输入从标准输入按以下格式给出： $N$ $M$ $x_1$ $y_1$ $z_1$ $x_2$ $y_2$ $z_2$ $:$ $:$ $x_N$ $y_N$ $z_N$

输出格式

输出 Ringo 选择的蛋糕集合能获得的（总美丽度的绝对值）+（总美味度的绝对值）+（总人气的绝对值）的最大可能值。

5 3
3 1 4
1 5 9
2 6 5
3 5 8
9 7 9

56

5 3
1 -2 3
-4 5 -6
7 -8 -9
-10 11 -12
13 -14 15

54

10 5
10 -80 21
23 8 38
-94 28 11
-26 -2 18
-69 72 79
-26 -86 -54
-72 -50 59
21 65 -32
40 -94 87
-62 18 82

638

3 2
2000000000 -9000000000 4000000000
7000000000 -5000000000 3000000000
6000000000 -1000000000 8000000000

30000000000

提示

$N$ 是一个在 $1$ 到 $1\ 000$（含）之间的整数。 $M$ 是一个在 $0$ 到 $N$（含）之间的整数。 $x_i, y_i, z_i \ (1 \leq i \leq N)$ 是在 $-10\ 000\ 000\ 000$ 到 $10\ 000\ 000\ 000$（含）之间的整数。考虑选择第 $2$、$4$ 和 $5$ 种蛋糕。此时总美丽度、总美味度和总人气如下：

美丽度：$1 + 3 + 9 = 13$ 美味度：$5 + 5 + 7 = 17$ 人气：$9 + 8 + 9 = 26$

此处（总美丽度的绝对值）+（总美味度的绝对值）+（总人气的绝对值）的值为 $13 + 17 + 26 = 56$。这是最大值。
考虑选择第 $1$、$3$ 和 $5$ 种蛋糕。此时总美丽度、总美味度和总人气如下：

美丽度：$1 + 7 + 13 = 21$ 美味度：$(-2) + (-8) + (-14) = -24$ 人气：$3 + (-9) + 15 = 9$

此处（总美丽度的绝对值）+（总美味度的绝对值）+（总人气的绝对值）的值为 $21 + 24 + 9 = 54$。这是最大值。
如果我们选择第 $3$、$4$、$5$、$7$ 和 $10$ 种蛋糕，总美丽度、总美味度和总人气将分别为 $-323$、$66$ 和 $249$。
此处（总美丽度的绝对值）+（总美味度的绝对值）+（总人气的绝对值）的值为 $323 + 66 + 249 = 638$。这是最大值。
蛋糕的美丽度、美味度和人气的值以及要输出的值可能不适合 32 位整数。

标签: AtCoder|abc100D

来源

AtCoder|abc100D