题目描述

蛋糕店有$N$块蛋糕，每块蛋糕有3个属性来描述相应的值，分别用$x$,$y$,$z$ 来表示。（$x,y,z为整数，当然可以为0，也可以为负数$）

现小X要挑选$M$块蛋糕，他想知道，如何挑选，能够保证这M块蛋糕的$x$属性累加和的绝对值+$y$属性累加和的绝对值+$z$属性累加和的绝对值 最大。

输入格式

第一行2个整数$N$ ,$M$（$1 \leq N \leq 1000$）,（$0 \leq M \leq N$）

接下来N行，每行3个整数 $x_i,y_i,z_i$ 表示每个蛋糕的相应属性 （$-1000000000 \leq x_i,y_i,z_i \leq 1000000000$ ）

输出格式

一个整数，表示我们要计算的最优值

样例数据

input

5 3
3 1 4
1 5 9
2 6 5
3 5 8
9 7 9

output

56

【样例解释】挑选第2,4,5 个蛋糕，可以得到56

input*

5 3
1 -2 3
-4 5 -6
7 -8 -9
-10 11 -12
13 -14 15

output

54

【样例解释】

挑选第1,3,5个可以得到最优

• x属性: 1+7+13=21
• y属性: (−2)+(−8)+(−14)=−24
• z属性: 3+(−9)+15=9

input

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

output

638

【样例解释】挑选第3,4,5,7,10个，可以得到最优

时间限制：$2 \text {s}$

空间限制：$256 \text {MB}$