AT_abc100_d [ABC100D] Patisserie ABC

[problemUrl]: https://atcoder.jp/contests/abc100/tasks/abc100_d 高橋君はプロのパティシエになり, 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 $

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

### 制約 - $ 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 整数に収まらない場合もある.