## 22536: Cup of Cowards

[提交][状态][讨论版][命题人:]

## 题目描述

Cup of Cowards (CoC) is a role playing game that has 5 different characters (Mage, Tank, Fighter,
Assassin and Marksman). A team consists of 5 players (one from each kind) and the goal is to kill a
monster withLlife points. The monster dies if the total damage it gets is at least L. Each character has
a certain number of allowed hits, each hit has a certain damage and a certain cost (the cost and damage
might be different for each character). The team wants to kill the monster using the minimum cost so
they can perform better in later missions. They want your help to nd the minimum cost they will pay
to kill the monster and the damage they should incur on it.

## 输入

Your program will be tested on one or more test cases. The rst line of the input will be a single integer
T, the number of test cases (1 T100). Followed by the test cases, the rst line of each test case
contains 1 integerL(0<=L<=10^12) representing the life points of the monster. Followed by 5 lines, each
one contains 3 integers separated by a single spaceH D Crepresenting the maximum number of hits,
the damage by each hit and the cost of each hit by one of the characters, respectively (0 H1,000),
(0 <=D, C<=109) and the sum of the maximum number of hits for all characters will not be more than
1,000.

## 输出

For each test case, print a single line which contains 2 space separated integers, the rst is the minimum
cost for the hits used to kill the monster and the second is the damage incurred upon the monster. If
there is more than one way to kill the monster using the same minimum cost, select the one with the least
damage and if there is no way to kill the monster print "We are doomed!!"(without the quotes).

## 样例输入

2
33
2 3 4
3 1 2
4 3 2
1 7 1
3 4 2
51
3 3 1
4 3 2
2 3 3
3 1 4
5 2 3

## 样例输出

19 33
We are doomed!!

[提交][状态]