[ZOJ1638]贪婪之岛

Grade Open Time Friday, 19 September 2014, 10:08 am
Discount 0.8 Time Discount Friday, 26 September 2014, 10:08 am
Allow late Yes Close Time Friday, 26 September 2014, 10:08 am
Input file greedyisland.in Output file greedyisland.out

【题目描述】

Gon和Killua正在进行一场贪婪之岛的游戏。游戏的目标是收集100张分散在整个游戏中的魔法卡片。一张卡片有三种能力:攻击,防御和特殊技能。每种能力的数值在[0,100]之间。每张卡只能使用一次,这一次只能使用一种能力。所有的卡片必须被储存在书——游戏的初始物品——中。书至多能储存50张卡片,因此Gon和Killua可以总共拥有之多100张卡片。现在Gon和Killua有n张卡片,并且他们想用A张来攻击,B张来防御,C张使用特殊技能(A+B+C<=100),如果n>A+B+C,他们就必须丢弃一些卡片。

他们想要知道“进攻”组卡片的进攻能力值和,“防御”组卡片的防御能力值和,“特殊技能”组卡片的特殊技能能力值和,这三者的最大和,以及在这个和达到最大时,所有卡片的所有能力和的最大值。

【输入格式】

输入包含多组数据。

输入文件的第一行有一个整数T(1<=T<=10),代表数据组数。

对于每组数据,第一行有一个整数n(n<=100000),第二行有三个整数A,B,C(A,B,C>=0,A+B+C<=n)。

接下来的n行每行有三个正整数,分别代表该卡片的进攻,防御和特殊能力值。

【输出格式】

对每组数据,输出一行两个正整数,即选取的A+B+C张卡片相应能力的之最大值,与相应能力和达到最大时所有能力和的最大值。

【样例输入】


2

3

1 1 1

100 0 0

0 100 0

0 0 100

4

1 1 1

12 32 44

33 48 37

37 38 33

46 79 78


【样例输出】

300 300

163 429


【提示】

样例解释:

第一组样例,选所有三张卡,第一张用于攻击,第二张用于防御,第三张用于特殊技能,相应能力值和是300,所有能力值和也是300.

第二组样例,选后三张卡,第二张用于防御,第三张用于攻击,第四章用于个数技能,相应能力值和是48+37+78=163,所有能力值和是(33+48+37)+(37+38+33)+(46+79+78)=429

【来源】


Author: JIANG, Jiefeng

Source: Zhejiang University Local Contest 2003

ZOJ 1638 Greedy Island