Cup of Cowards

Cup of Cowards (CoC) is a role playing game with five character classes: mage, tank, fighter, assassin and marksman. A team is five players, one of each class, and their goal is to kill a monster with $L$ life points. The monster dies once the total damage it has taken is at least $L$.

Every character may hit only a limited number of times. All hits of one character deal the same damage and cost the same amount, but the damage and the cost may differ from character to character. The team wants to pay as little as possible so they do better in later missions. Find the minimum cost the team pays to kill the monster, and the damage they deal to it.

The first line has one integer $T$, the number of test cases ($1 \le T \le 100$).

The first line of each test case has one integer $L$, the life points of the monster ($0 \le L \le 10^{12}$). Five lines follow, one per character, each with three integers $H$, $D$ and $C$ separated by single spaces: the maximum number of hits, the damage of one hit and the cost of one hit ($0 \le H \le 1000$, $0 \le D, C \le 10^9$). The five values of $H$ add up to at most $1000$.

For each test case print one line with two integers separated by a space. The first is the minimum cost of the hits that kill the monster, the second is the damage those hits deal. If several plans reach the minimum cost, choose the one that deals the least damage. When $L$ is $0$ the team needs no hit, so print 0 0. If no set of hits can kill the monster, print We are doomed!!.