分数: 400 点
问题陈述
高桥成为糕点师并开了一家店 ABC 糖果厂 庆祝 AtCoder 初学者大赛第 100 届。
本店有售 N 各种蛋糕。
每种蛋糕都有“美观”、“美味”和“受欢迎”三个参数。的 i第一种蛋糕有这样的美感 x_i,味道 y_i 和受欢迎程度 z_i.
这些值可能为零或负数。
林戈决定 M 这里有蛋糕。他会选择蛋糕套餐如下:
- 不要有两块或两块以上同一种蛋糕。
- 在上述条件下,选择最大化的蛋糕组(总美观的绝对值)+(总美味的绝对值)+(总人气的绝对值)。
找出林戈选择的蛋糕组(总美观的绝对值)+(总美味的绝对值)+(总人气的绝对值)的最大可能值。
约束
- N 是介于 1 和 1 \ 000 (含)。
- M 是介于 0 和 N (含)。
- x_i, y_i, z_i \ (1 \leq i \leq N) 是介于 -10 \ 000 \ 000 \ 000 和 10 \ 000 \ 000 \ 000 (含)。
输入
输入由标准输入按以下格式给出:
N M x_1 y_1 z_1 x_2 y_2 z_2 : : x_N y_N z_N
输出
打印林戈选择的蛋糕组的(总美观的绝对值)+(总美味的绝对值)+(总人气的绝对值)的最大可能值。
示例输入 1
5 3 3 1 4 1 5 9 2 6 5 3 5 8 9 7 9
示例输出 1
56
考虑拥有 2-nd, 4-th 和 5第几种蛋糕。总的美丽、美味和受欢迎程度如下:
- 美容: 1 + 3 + 9 = 13
- 美味: 5 + 5 + 7 = 17
- 受欢迎程度: 9 + 8 + 9 = 26
这里的数值(总颜值绝对值)+(总美味绝对值)+(总人气绝对值)为 13 + 17 + 26 = 56。这是最大值。
示例输入 2
5 3 1 -2 3 -4 5 -6 7 -8 -9 -10 11 -12 13 -14 15
示例输出 2
54
考虑拥有 1-st, 3-rd 和 5第几种蛋糕。总的美丽、美味和受欢迎程度如下:
- 美容: 1 + 7 + 13 = 21
- 美味: (-2) + (-8) + (-14) = -24
- 受欢迎程度: 3 + (-9) + 15 = 9
这里的数值(总颜值绝对值)+(总美味绝对值)+(总人气绝对值)为 21 + 24 + 9 = 54。这是最大值。
示例输入 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
示例输出 3
638
如果我们有 3-rd, 4-th, 5-th, 7-th 和 10第几种蛋糕,集美观、美味、人气于一身 -323, 66 和 249。
这里的数值(总颜值绝对值)+(总美味绝对值)+(总人气绝对值)为 323 + 66 + 249 = 638。这是最大值。
示例输入 4
3 2 2000000000 -9000000000 4000000000 7000000000 -5000000000 3000000000 6000000000 -1000000000 8000000000
示例输出 4
30000000000
蛋糕的美观度、美味度和受欢迎度的值以及要打印的值可能不适合 32 位整数。