题目描述

高橋君はプロのパティシエになり, AtCoder Beginner Contest 100 を記念して, 「ABC洋菓子店」というお店を開いた.

ABC洋菓子店では, $N$ 種類のケーキを売っている.
各種類のケーキには「綺麗さ」「おいしさ」「人気度」の $3$ つの値を持ち, $i$ 種類目のケーキの綺麗さは $x_i$, おいしさは $y_i$, 人気度は $z_i$ である.
これらの値は $0$ 以下である可能性もある.

りんごさんは, ABC洋菓子店で $M$ 個のケーキを食べることにした. 彼は次のように, 食べるケーキの組み合わせを選ぶことにした.

• 同じ種類のケーキを $2$ 個以上食べない.
• 上の条件を満たしつつ, (綺麗さの合計の絶対値) + (おいしさの合計の絶対値) + (人気度の合計の絶対値) が最大になるように選ぶ.

このとき, りんごさんが選ぶケーキの (綺麗さの合計の絶対値) + (おいしさの合計の絶対値) + (人気度の合計の絶対値) の最大値を求めなさい.

输入格式

入力は以下の形式で標準入力から与えられる.

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

输出格式

りんごさんが選ぶケーキの (綺麗さの合計の絶対値) + (おいしさの合計の絶対値) + (人気度の合計の絶対値) の最大値を出力しなさい.

题目大意

有三个序列 $a,b,c$，长度是 $n$，然后让你求 $1 \sim n$ 的一个长度为 $m$ 的子序列 $t_1 \sim t_m$，满足 $|\sum\limits_{i=1}^m a_{t_i}|+|\sum\limits_{i=1}^m b_{t_i}|+|\sum\limits_{i=1}^m c_{t_i}|$ 最大。其中 $|x|$ 指的是绝对值。

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$ 以下の整数.

Sample Explanation 1

$2,\ 4,\ 5$ 種類目のケーキを食べることを考える. そのとき, 「綺麗さ」「おいしさ」「人気度」の合計はそれぞれ次のようになる. - 綺麗さ：$1\ +\ 3\ +\ 9\ =\ 13$ - おいしさ：$5\ +\ 5\ +\ 7\ =\ 17$ - 人気度：$9\ +\ 8\ +\ 9\ =\ 26$ このときの (綺麗さの合計の絶対値) + (おいしさの合計の絶対値) + (人気度の合計の絶対値) は $13\ +\ 17\ +\ 26\ =\ 56$ となり, これが最大になる.

Sample Explanation 2

$1,\ 3,\ 5$ 種類目のケーキを食べることを考える. そのとき, 「綺麗さ」「おいしさ」「人気度」の合計はそれぞれ次のようになる. - 綺麗さ：$1\ +\ 7\ +\ 13\ =\ 21$ - おいしさ：$(-2)\ +\ (-8)\ +\ (-14)\ =\ -24$ - 人気度：$3\ +\ (-9)\ +\ 15\ =\ 9$ このときの (綺麗さの合計の絶対値) + (おいしさの合計の絶対値) + (人気度の合計の絶対値) は $21\ +\ 24\ +\ 9\ =\ 54$ となり, これが最大になる.

Sample Explanation 3

$3,\ 4,\ 5,\ 7,\ 10$ 種類目のケーキを食べると, 綺麗さの合計は $-323$, おいしさの合計は $66$, 人気度の合計は $249$ となる. このときの (綺麗さの合計の絶対値) + (おいしさの合計の絶対値) + (人気度の合計の絶対値) は $323\ +\ 66\ +\ 249\ =\ 638$ となり, これが最大になる.

Sample Explanation 4

ケーキの綺麗さ, おいしさ, 人気度や出力すべき値が, 32bit 整数に収まらない場合もある.