100 #ABC100D. [ABC100D] Patisserie ABC

[ABC100D] Patisserie ABC

题目描述

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

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

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

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

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

输入格式

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

N N M M x1 x_1 y1 y_1 z1 z_1 x2 x_2 y2 y_2 z2 z_2 : : : : xN x_N yN y_N zN z_N

输出格式

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

题目大意

有三个序列 a,b,ca,b,c,长度是 nn,然后让你求 1n1 \sim n 的一个长度为 mm 的子序列 t1tmt_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|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 N 1 1 以上 1 000 1\ 000 以下の整数
  • M M 0 0 以上 N N 以下の整数
  • xi, yi, zi (1  i  N) x_i,\ y_i,\ z_i\ (1\ \leq\ i\ \leq\ N) は, それぞれ 10 000 000 000 -10\ 000\ 000\ 000 以上 10 000 000 000 10\ 000\ 000\ 000 以下の整数.

Sample Explanation 1

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

Sample Explanation 2

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

Sample Explanation 3

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

Sample Explanation 4

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