程序能力实训(BY) 热身1

D. 康康与24层魔塔

单点时限: 2.0 sec

内存限制: 512 MB

魔塔”三原版”就是50层魔塔,24层魔塔和新新魔塔,其中24层魔塔是”三原版”中最简单的一部,也是大多数魔塔玩家最早接触的魔塔。

康康因为出题过于无聊,因此玩起了24层魔塔,重温童年的乐趣。

康康最开始拥有$H_1$点生命,$G_1$点攻击和$F_1$点防御。而怪物最开始拥有$H_2$点生命,$G_2$点攻击,和$F_2$点防御。

康康和怪物进行战斗时,康康会首先攻击,然后怪物进行攻击,康康再进行攻击......双方交替进行攻击,直至战斗结束。康康和怪物每次攻击时,被攻击方会扣除(对方的攻击-自己的防御)点生命值,如果一方的生命值小于等于0,战斗立即结束。如果一方的攻击力小于等于另一方的防御,则攻击不会扣除生命值。

现在康康拥有$K$次提高能力的机会,每次提高能力时,可以从”增加800点生命“,”增加4点攻击“,”增加4点防御“中选择一个。康康想知道自己可以在击败怪物后剩下最多多少生命值。

输入格式

第一行包括一个整数T,代表数据组数。

接下来T行,每行分别是$H_1$,$G_1$,$F_1$,$H_2$,$G_2$,$F_2$,$K$七个整数,含义见题目描述。

输出格式

对于每组数据输出一行,代表康康最多剩下的生命值。如果康康无法击败怪物,输出-1。

样例

Input
7
100 10 0 100 10 0 0
100 16 0 100 10 10 1
100 10 0 99999 4 9 1
100 10 0 100 10 0 1
100 10 100 100 10 100 5
100 10 10 1000 1000 0 3
100 1 1 100 0 0 0
Output
10
740
100
810
-1
-1
100

提示

对于40%的数据,$K=0$

对于60%的数据,$H_1$,$G_1$,$F_1$,$H_2$,$G_2$,$F_2$,$K \le 100$

对于80%的数据,$H_1$,$G_1$,$F_1$,$H_2$,$G_2$,$F_2$,$K \le 10000$

对于100%的数据,$H_1$,$G_1$,$F_1$,$H_2$,$G_2$,$F_2$,$K \le 1000000$,$T \le 10$