题目描述

有三个序列 $a,b,c$，长度都是 $n$。现在你要构造数列 $\{1,2,3,\cdots,n\}$ 的一个子序列 $t$，且长度为 $m$。构造的方法有很多，你需要输出所有构造方案中

$$|\sum_{i=1}^ma_{t_i}|+|\sum_{i=1}^mb_{t_i}|+|\sum_{i=1}^mc_{t_i}| $$

的最大值。

输入格式

第一行两个数 $n,m$。

往下总共 $n$ 行，每一行有三个数，其中第 $i$ 行的三个数分别是 $a_i,b_i,c_i$。

输出格式

按照题目要求输出。

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

数据范围

• $1\le n\le 1000$
• $0\le m\le n$
• 序列内数的绝对值小于等于 $10^9$