3876 - 项目指标

题目描述

某大型企业正在组织一个重要的项目,每个项目分为三个考核方面:技术开发、市场推广和运营管理。

企业记录了过去 n 次任务中项目组在这三个方面的表现得分,分别形成了三个长度为 n 的序列:abc,其中第 i 项任务的得分为 a_ib_ic_i。这些得分可能小于等于 0

项目组只能从这些任务中任意选取 m 项任务,形成样本,用于分析团队的表现。你需要选择其中 m 个任务 t_1 \sim t_m使得下面的目标值最大化:

技术开发能力总和的绝对值 + 市场推广总和的绝对值 + 运营管理能力总和的绝对值。

请你帮助企业完成这一分析任务。

输入

输入格式如下:

1 行包含两个整数 nm

2 行到第 n+1 行,每行包含三个整数,表示项目组在某个任务中三项指标的表现。

输出

输出选择的 m 个任务的:(技术开发总和的绝对值)+(市场推广总和的绝对值)+(运营管理总和的绝对值)的最大可能值。

样例

输入

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

输出

56

输入

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

输出

54

输入

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
说明

样例 1 解释

可以选择第 245 个任务。

  • 总的技术开发指标:1 + 3 + 9 = 13
  • 总的市场推广指标:5 + 5 + 7 = 17
  • 总的运营管理指标:9 + 8 + 9 = 26

这里的值为 13 + 17 + 26 = 56。这是可能得到的最大值。

样例 2 解释

可以选择第 13 和第 5 个任务。

  • 总的技术开发指标:1 + 7 + 13 = 21

  • 总的市场推广指标:(-2) + (-8) + (-14) = -24

  • 总的运营管理指标:3 + (-9) + 15 = 9

这里的值为 21 + 24 + 9 = 54。这是可能得到的最大值。

样例 3 解释

可以选择第 3457 和第 10 个任务。(总的技术开发指标)+(总的市场推广指标的绝对值)+(总的运营管理指标的绝对值)为 323 + 66 + 249 = 638

数据规模

对于所有的测试数据,满足 1 \leq n \leq 1000 0 \leq m \leq n -10^{10} \leq a_i,b_i,c_i \leq 10^{10}

测试点特殊性质
1 \sim 2A
3 \sim 8B
9 \sim 20
  • 特殊性质 A:满足 m \le 1

  • 特殊性质 B:满足 na_i 的正负性全部相同, nb_i 的正负性全部相同, nc_i 的正负性全部相同。

标签
题目参数
时间限制 1 秒
内存限制 256 MB
提交次数 0
通过人数 0
金币数量 2 枚
难度 基础


上一题 下一题