겁쟁이의 컵

겁쟁이의 컵(Cup of Cowards, CoC)은 마법사, 탱커, 전사, 암살자, 궁수 다섯 직업이 등장하는 롤플레잉 게임이다. 한 팀은 직업마다 한 명씩 다섯 명으로 이루어지고, 목표는 생명력이 $L$인 몬스터를 잡는 것이다. 몬스터가 받은 피해량의 합이 $L$ 이상이 되면 몬스터는 죽는다.

캐릭터마다 공격할 수 있는 횟수가 정해져 있다. 같은 캐릭터의 공격은 모두 피해량이 같고 비용도 같지만, 피해량과 비용은 캐릭터마다 다를 수 있다. 팀은 이후 임무를 더 잘 치르려고 최소 비용으로 몬스터를 잡으려 한다. 몬스터를 잡는 데 드는 최소 비용과 그때 몬스터에게 주는 피해량을 구하라.

첫 줄에 테스트 케이스의 개수 $T$가 주어진다 ($1 \le T \le 100$).

각 테스트 케이스의 첫 줄에는 몬스터의 생명력 $L$이 주어진다 ($0 \le L \le 10^{12}$). 이어지는 다섯 줄에는 캐릭터 한 명의 정보가 세 정수 $H$, $D$, $C$로 주어지고, 공백 하나로 구분된다. 순서대로 최대 공격 횟수, 공격 한 번의 피해량, 공격 한 번의 비용이다 ($0 \le H \le 1000$, $0 \le D, C \le 10^9$). 다섯 캐릭터의 $H$를 모두 더한 값은 $1000$ 이하이다.

각 테스트 케이스마다 한 줄에 두 정수를 공백으로 구분해 출력한다. 첫 번째 수는 몬스터를 잡는 데 드는 최소 비용이고, 두 번째 수는 그때 몬스터에게 주는 피해량이다. 최소 비용으로 잡는 방법이 여러 가지면 피해량이 가장 적은 방법을 고른다. $L$이 $0$이면 공격이 필요 없으므로 0 0을 출력한다. 어떻게 공격해도 몬스터를 잡을 수 없으면 We are doomed!!를 출력한다.