该比赛已结束，您无法在比赛模式下递交该题目。您可以点击“在题库中打开”以普通模式查看和递交本题。

魔塔谜题

时间限制：2 s

空间限制：256 MiB

题目背景

pzr 喜欢玩魔塔游戏。但是他并不熟悉加点和转换操作，总是不能选择较优路线。

在学习了 C 语言后，他希望使用编程方法，决定最终方案。

题目描述

现在，我们考虑一个简化版的问题。

勇者必须击败前方的 $1$ 个魔物。勇者的攻击力是 $ATK_1$，防御力是 $DEF_1$，生命值为 $HP_1$。魔物的攻击力是 $ATK_2$，防御力是 $DEF_2$，生命值是 $HP_2$。

战斗分为若干轮，每一轮的过程可描述如下：

• 首先，勇者攻击魔物，造成 $\max(0, ATK_1-DEF_2)$ 点伤害。于是，魔物的生命值降低 $\max(0, ATK_1-DEF_2)$。如果操作后魔物的生命值降低为 $0$ 或以下，则勇者获得胜利。
• 接下来，魔物攻击勇者，造成 $\max(0, ATK_2-DEF_1)$ 点伤害。于是，勇者的生命值降低 $\max(0, ATK_2-DEF_1)$。如果操作后勇者的生命值降低为 $0$ 或以下，则勇者在战斗中失败。

在战斗前，勇者可以在商店中购买能力值。勇者拥有的金币最多可以执行 $N$ 次能力值购买操作，每次操作选择以下三项之一：

• 购买一颗红色宝石，攻击力增加 $A$
• 购买一颗蓝色宝石，防御力增加 $D$
• 购买一颗绿色宝石，生命值增加 $H$

请问，勇者能否通过能力值购买，最终击败魔物？如果可以，请输出战斗后生命值的最大值。如果不能，请输出 $-1$。

输入格式

本题共 $T$ 组测试数据。

对于每组测试数据，包含一行 $10$ 个非负整数 $ATK_1,DEF_1,HP_1,ATK_2,DEF_2,HP_2,N,A,D,H$。

输出格式

对于每组测试数据，如果勇者能够通过能力值购买最终击败魔物，则输出战斗后生命值的最大值。如果不能，请输出 $-1$。

样例输入1

5
300 200 2000 800 150 1000 1 100 150 2000
800 200 6000 5000 300 700 2 100 150 2000
800 200 6000 1000 1000 300 2 100 150 2000
1000 2000 3000 1800 570 100000 1000000000 1000000000 1000000000 1000000000 
1000 5000 2000 2000 6000 2000 1 10 10 10

样例输出1

400
6000
-1
1000000000000003000
-1

样例1解释

对于第一组测试数据： 勇者的攻击力为 300，防御力为 200，生命值为 2000

魔物的攻击力为 800，防御力为 150，生命值为 1000

勇者一共可以购买一次能力值，选择以下一项：

• 攻击力提升 $100$
• 防御力提升 $150$
• 生命值提升 $2000$

如果选择第一项，则勇者的攻击力提升至 $400$，他每回合可以对魔物造成 $\max(0,400-150)=250$ 点伤害，每回合受到 $\max(0,800-200)=600$ 点伤害。

三轮攻击过后，勇者共造成 $750$ 点伤害，受到 $1800$ 点伤害。第四轮开始后，勇者再造成 $250$ 点伤害，魔物的生命值降低到 $0$，所以战斗结束，勇者共受到 $1800$ 点伤害，剩余 $200$ 点生命值。

如果选择第二项，则勇者的防御力提升至 $350$，他每回合可以对魔物造成 $\max(0,300-150)=150$ 点伤害，每回合受到 $\max(0,800-350)=450$ 点伤害。

在第五轮结束后，勇者共造成 $750$ 点伤害，魔物共造成 $2250$ 点伤害，勇者的生命值降低至 $-250$，但魔物还剩余 $250$ 点生命值，因此输掉战斗。

如果选择第三项，则勇者的生命值提升至 $4000$，他每回合可以对魔物造成 $\max(0,300-150)=150$ 点伤害，每回合受到 $\max(0,800-200)=600$ 点伤害。

在第六轮结束后，勇者共造成 $900$ 点伤害，魔物共造成 $3600$ 点伤害，第七轮开始后，勇者再造成 $150$ 点伤害，魔物的生命值降低到 $-50$，所以战斗结束，勇者共受到 $3600$ 点伤害，剩余 $400$ 点生命值。

因此，选择第三项，剩余 $400$ 点生命值。

对于第二组测试数据，加两次攻击，可以在第一轮击败魔物。

对于第三组测试数据，勇者不能击破魔物的防御，因此无法打败魔物。

对于第四组测试数据，魔物不能击破勇者的防御，所有金币用来加生命值。

对于第五组测试数据，注意，如果双方都不能击破对方防御，则战斗无法结束，勇者无法击败魔物。

注意，答案可能超过 $32$ 位整数能够表示的范围。

数据范围及约定

对于 $30\%$ 的数据，$T=10，N=1, 1\le ATK_1,DEF_1,ATK_2,DEF_2,HP_1,HP_2,A,D,H\le 10^3$。

对于 $60\%$ 的数据，$T=10，1\le ATK_1,DEF_1,ATK_2,DEF_2,HP_1,HP_2,N,A,D,H\le 10^6$。

对于 $100\%$ 的数据，$1\le T\le 10^3$,$1\le ATK_1,DEF_1,ATK_2,DEF_2,HP_1,HP_2,N,A,D,H\le 10^9$。