Cup of Cowards (CoC) 是一款角色扮演游戏，拥有 5 种不同的角色（法师、坦克、战士、刺客和射手）。一个团队由 5 名玩家组成（每种角色各一名），目标是击杀拥有 $L$ 点生命值的怪物。如果怪物受到的总伤害至少为 $L$，则怪物死亡。每个角色都有一定的允许攻击次数，每次攻击都有一定的伤害值和一定的代价（不同角色的代价和伤害可能不同）。团队希望以最小的代价击杀怪物，以便在后续任务中表现更好。他们需要你的帮助，找出击杀怪物所需的最小代价以及他们应对怪物造成的伤害。

输入格式

你的程序将在一个或多个测试用例上进行测试。输入的第一行是一个整数 $T$，表示测试用例的数量（$1 \le T \le 100$）。接下来是各个测试用例，每个测试用例的第一行包含 1 个整数 $L$（$0 \le L \le 10^{12}$），表示怪物的生命值。随后有 5 行，每行包含 3 个由空格分隔的整数 $H$、$D$、$C$，分别代表该角色的最大攻击次数、每次攻击的伤害以及每次攻击的代价（$0 \le H \le 1,000$，$0 \le D, C \le 10^9$），且所有角色最大攻击次数之和不超过 $1,000$。

输出格式

对于每个测试用例，输出一行，包含两个由空格分隔的整数，第一个是击杀怪物所用的最小代价，第二个是怪物受到的伤害。如果存在多种以相同最小代价击杀怪物的方法，请选择伤害最小的那一种；如果无法击杀怪物，则输出 "We are doomed!!"（不含引号）。

样例

输入 1

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

输出 1

19 33
We are doomed!!