← 返回题目列表

AtCoder · abc100_d

D. 糕点店 ABC

中文机器翻译题面 查看原题

分数: 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 位整数。