Задача 38623. Cake set

Wushan from the planet Blook opened a bakery. His bakery sells N kinds of cakes. Each type of cake has three parameters: "beauty", "taste" and "popularity". The 1st kind of cake has xi beauty, yi flavor and zi popularity. These values ​​can be zero or negative.
Gromozeka decided that he would buy M pieces of cake. It selects a set like this:
- You cannot use two or more pieces of the same type of cake.
- With the above condition, the set of cakes that maximizes (absolute overall beauty value) + (absolute overall taste value) + (absolute overall popularity value) is selected.
Find the maximum possible value (total beauty absolute value) + (total taste absolute value) + (total popularity absolute value) for the set of cakes Gromozeka chooses.

Input
The first line contains two space-separated integers N (1<=N<=1000) and M (0<=M<=N). The next N lines contain   three integers xi, yi and zi (-10⁹<=xi, yi, zi <=10⁹, 1<=i<=N).< br />
Imprint
Print the maximum possible value (absolute value of overall beauty) + (absolute value of overall taste) + (absolute value of overall popularity) for the set of cakes Gromozeka chooses.
 

 

Examples

#	Input	Output	Explanation
1	5 3 3 1 4 1 5 9 2 6 5 3 5 8 9 7 9	56	Think about the 2nd, 4th and 5th types of cakes. The overall beauty, taste and popularity will be as follows: Beauty: 1 + 3 + 9 = 13 Taste: 5 + 5 + 7 = 17 Popularity: 9 + 8 + 9 = 26 The value (absolute value of overall beauty) + (absolute value of overall palatability) + (absolute value of overall popularity) here is 13 + 17 + 26 = 56. This is the maximum value.
2	5 3 1-2 3 -4 5 -6 7-8-9 -10 11 -12 13-14 15	54	Consider having 1st, 3rd and 5th types of cakes. The overall beauty, taste and popularity will be as follows: Beauty: 1 + 7 + 13 = 21 Taste: (−2) + (- 8) + (- 14) = - 24 Popularity: 3 + (- 9) + 15 = 9 The value (absolute value of overall beauty) + (absolute value of overall palatability) + (absolute value of overall popularity) here is 21 + 24 + 9 = 54. This is the maximum value.
3	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	If we have 3rd, 4th, 5th, 7th and 10th kinds of cakes, the overall beauty, taste and popularity will be -323, 66 and 249 respectively. The value of (total beauty absolute value) + (total palatability absolute value) + (total popularity absolute value) here is 323 + 66 + 249 = 638. This is the maximum value.
4	3 2 2000000000 -9000000000 4000000000 7000000000 -5000000000 3000000000 6000000000 -1000000000 8000000000	30000000000	The beauty, flavor, and popularity values ​​of the cakes, as well as the value to be printed, may not correspond to 32-bit integers.