题目描述

高桥君成为了一名专业的糕点师，为纪念 AtCoder Beginner Contest 100，开设了一家名为“ABC洋菓子店”的店铺。

在 ABC洋菓子店中，售卖 $N$ 种类的蛋糕。 每种蛋糕都有“美丽度”“美味度”“人气度”这三个数值，第 $i$ 种蛋糕的美丽度为 $x_i$，美味度为 $y_i$，人气度为 $z_i$。 这些数值也有可能小于等于 $0$。

りんごさん决定在 ABC洋菓子店吃 $M$ 个蛋糕。他选择蛋糕的方式如下：

• 不会吃同一种蛋糕两次及以上。
• 在满足上述条件的前提下，选择使（美丽度总和的绝对值）+（美味度总和的绝对值）+（人气度总和的绝对值）最大的组合。

请你求出りんごさん所能选择的蛋糕的（美丽度总和的绝对值）+（美味度总和的绝对值）+（人气度总和的绝对值）的最大值。

输入格式

输入以如下格式从标准输入读入。

$N$ $M$
$x_1$ $y_1$ $z_1$
$x_2$ $y_2$ $z_2$
$\vdots$
$x_N$ $y_N$ $z_N$

输出格式

请输出りんごさん所能选择的蛋糕的（美丽度总和的绝对值）+（美味度总和的绝对值）+（人气度总和的绝对值）的最大值。

输入输出样例 #1

输入 #1

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

输出 #1

56

输入输出样例 #2

输入 #2

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

输出 #2

54

输入输出样例 #3

输入 #3

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

输出 #3

638

输入输出样例 #4

输入 #4

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

输出 #4

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$ 之间的整数。

样例解释 1

考虑吃第 $2$、$4$、$5$ 种蛋糕时，“美丽度”“美味度”“人气度”的总和分别如下：

• 美丽度：$1 + 3 + 9 = 13$
• 美味度：$5 + 5 + 7 = 17$
• 人气度：$9 + 8 + 9 = 26$ 此时（美丽度总和的绝对值）+（美味度总和的绝对值）+（人气度总和的绝对值）为 $13 + 17 + 26 = 56$，这是最大的。

样例解释 2

考虑吃第 $1$、$3$、$5$ 种蛋糕时，“美丽度”“美味度”“人气度”的总和分别如下：

• 美丽度：$1 + 7 + 13 = 21$
• 美味度：$(-2) + (-8) + (-14) = -24$
• 人气度：$3 + (-9) + 15 = 9$ 此时（美丽度总和的绝对值）+（美味度总和的绝对值）+（人气度总和的绝对值）为 $21 + 24 + 9 = 54$，这是最大的。

样例解释 3

如果吃第 $3$、$4$、$5$、$7$、$10$ 种蛋糕，美丽度总和为 $-323$，美味度总和为 $66$，人气度总和为 $249$。 此时（美丽度总和的绝对值）+（美味度总和的绝对值）+（人气度总和的绝对值）为 $323 + 66 + 249 = 638$，这是最大的。

样例解释 4

蛋糕的美丽度、美味度、人气度以及输出的值，有可能超出 32 位整数的范围。

由 ChatGPT 4.1 翻译