某大型企业正在组织一个重要的项目,每个项目分为三个考核方面:技术开发、市场推广和运营管理。
企业记录了过去 n 次任务中项目组在这三个方面的表现得分,分别形成了三个长度为 n 的序列:a、b 和 c,其中第 i 项任务的得分为 a_i、b_i 和 c_i。这些得分可能小于等于 0。
项目组只能从这些任务中任意选取 m 项任务,形成样本,用于分析团队的表现。你需要选择其中 m 个任务 t_1 \sim t_m,使得下面的目标值最大化:
技术开发能力总和的绝对值 + 市场推广总和的绝对值 + 运营管理能力总和的绝对值。
请你帮助企业完成这一分析任务。
输入格式如下:
第 1 行包含两个整数 n 和 m。
第 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
可以选择第 2、4 和 5 个任务。
这里的值为 13 + 17 + 26 = 56。这是可能得到的最大值。
可以选择第 1、3 和第 5 个任务。
总的技术开发指标:1 + 7 + 13 = 21
总的市场推广指标:(-2) + (-8) + (-14) = -24
总的运营管理指标:3 + (-9) + 15 = 9
这里的值为 21 + 24 + 9 = 54。这是可能得到的最大值。
可以选择第 3、4、5 、7 和第 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 2 | A |
| 3 \sim 8 | B |
| 9 \sim 20 | 无 |
特殊性质 A:满足 m \le 1。
特殊性质 B:满足 n 个 a_i 的正负性全部相同, n 个 b_i 的正负性全部相同, n 个 c_i 的正负性全部相同。