ABC 点心店

题目描述

高桥君成为了一名职业甜点师,为了纪念 AtCoder Beginner Contest 100,他开了一家名为「ABC 洋果子店」的店。

ABC 洋果子店出售 $N$ 种蛋糕。

每种蛋糕都有「美观度」「美味度」「人气度」$3$ 个值,第 $i$ 种蛋糕的美观度为 $x_i$,美味度为 $y_i$,人气度为 $z_i$。

这些值也可能不超过 $0$。

Ringo 君决定在 ABC 洋果子店吃 $M$ 个蛋糕。他按照以下方式选择要吃的蛋糕组合。

• 同一种类的蛋糕不能吃 $2$ 个以上。
• 在满足上述条件的前提下,选择使 (美观度总和的绝对值) + (美味度总和的绝对值) + (人气度总和的绝对值) 最大的组合。

此时,请找出 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

考虑吃第 $2, 4, 5$ 种蛋糕。此时,「美观度」「美味度」「人气度」的总和分别如下。

• 美观度:$1 + 3 + 9 = 13$
• 美味度:$5 + 5 + 7 = 17$
• 人气度:$9 + 8 + 9 = 26$

此时 (美观度总和的绝对值) + (美味度总和的绝对值) + (人气度总和的绝对值) 为 $13 + 17 + 26 = 56$,这是最大值。

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

54

考虑吃第 $1, 3, 5$ 种蛋糕。此时,「美观度」「美味度」「人气度」的总和分别如下。

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

此时 (美观度总和的绝对值) + (美味度总和的绝对值) + (人气度总和的绝对值) 为 $21 + 24 + 9 = 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, 4, 5, 7, 10$ 种蛋糕时,美观度总和为 $-323$,美味度总和为 $66$,人气度总和为 $249$。

此时 (美观度总和的绝对值) + (美味度总和的绝对值) + (人气度总和的绝对值) 为 $323 + 66 + 249 = 638$,这是最大值。

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

30000000000

蛋糕的美观度、美味度、人气度以及应输出的值,有时可能无法放入 32 位整数中。

数据范围

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