题目描述

Takahashi became a pastry chef and opened a shop La Confiserie d'ABC to celebrate AtCoder Beginner Contest 100.

The shop sells $N$ kinds of cakes.
Each kind of cake has three parameters "beauty", "tastiness" and "popularity". The $i$-th kind of cake has the beauty of $x_i$, the tastiness of $y_i$ and the popularity of $z_i$.
These values may be zero or negative.

Ringo has decided to have $M$ pieces of cakes here. He will choose the set of cakes as follows:

• Do not have two or more pieces of the same kind of cake.
• Under the condition above, choose the set of cakes to maximize (the absolute value of the total beauty) + (the absolute value of the total tastiness) + (the absolute value of the total popularity).

Find the maximum possible value of (the absolute value of the total beauty) + (the absolute value of the total tastiness) + (the absolute value of the total popularity) for the set of cakes that Ringo chooses.

高桥成为一名糕点师，为了庆祝 AtCoder 第 100 届初学者竞赛，他开设了一家名为 "La Confiserie d'ABC" 的店铺。

店里出售 $N$ 种蛋糕。
每种蛋糕都有 "美观"、"美味 "和 "受欢迎 "三个参数。 第 $i$ 种蛋糕的美观度为 $x_i$ ，美味度为 $y_i$ ，受欢迎度为 $z_i$ 。
这些值可能是零，也可能是负值。

林戈决定在这里吃 $M$ 块蛋糕。他将选择以下一组蛋糕：

• 不要有两块或两块以上的同类蛋糕。
• 在上述条件下，选择一组蛋糕，使（总美感的绝对值）+（总美味的绝对值）+（总受欢迎程度的绝对值）最大。

求林果选择的这组蛋糕的（总美感的绝对值）+（总美味的绝对值）+（总受欢迎程度的绝对值）的最大可能值。

输入格式

输入内容按以下格式标准输入：

$N$ $M$
$x_1$ $y_1$ $z_1$
$x_2$ $y_2$ $z_2$
$:$ $:$
$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 位整数表示。