Problem A: Delicious cake

Problem A: Delicious cake

Time Limit: 1 Sec  Memory Limit: 128 MB
Submit: 70  Solved: 21
[Submit] [Status] [Web Board] [Creator:]

Description

这一天终于迎来了lx学长的生日,因为学长人缘很好,所以有很多人送给他蛋糕,他现在拥有n个蛋糕,每个蛋糕都有a[i],b[i],c[i],三种营养数值,可能是正的可能是负的也可能为0,学长的肚子只能只有m的容量,那现在他想要选择m个蛋糕,要求有以下规则:

每个相同的蛋糕不能吃两个
并且他想要达到通过吃m个蛋糕来获得最多的营养价值 total = abs(所选m个蛋糕的a[i]的和) + abs(所选m个蛋糕的b[i]的和) + abs(所选m个蛋糕的c[i]的和)
每个蛋糕的容量都为1

lx想要获得最大的营养价值,因为lx学长想快快长高(hhhha),请你来帮助lx学长求一下他可能获得的最大营养价值的和是多少


 

Input

第一行t,代表测试数组的组数  (1 <= t <= 10)

每组数组第一行有n,m,分别代表n个蛋糕,和学长肚子的容量m. (1 <= n <= 1000,0 <= m <= n)

下面n行,a[i],b[i],c[i],分别代表着第i个蛋糕的三个营养数值,

(-10,000,000,000<= a[i],b[i],c[i] <= 10,000,000,000)

Output

输出,对于每组测试数据输出学长可以获得的最大营养价值

Sample Input Copy

3
5 3
1 2 3
4 5 6
7 8 9
10 11 12
14 15 16
3 2 
1 100 50
99 2 3 
4 200 -60
5 3
1 -2 3
-4 5 -6
7 -8 -9
-10 11 -12
13 -14 15

Sample Output Copy

102
362
54