题目描述

有三个序列 $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|$ 指的是绝对值。

输入格式

第一行两个整数 $N, M$。

接下来 $N$ 行，每行三个正整数 $x_i, y_i, z_i$，分别表示序列 ${x}, {y}, {z}$。

$1 \le N \le 1000$，$0 \le M \le N$，$-10^9 \le x_i, y_i, z_i \le 10^9$。

输出格式

一个正整数表示答案。

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