题目描述

《王国英雄》是一款点击解谜类的冒险游戏。游戏中的主人公为了拯救他/她的父亲，踏上了一段危险的旅途，并成为了王国的英雄。

:::align{center} :::

游戏中的货币被称为“金币”，可以用于购买各种补给品，甚至还能用于完成特定任务。俗话说得好，“钱永远不嫌多”，我们的天才玩家堡堡刚刚就找到了一种变得富有的方法。游戏中有一座磨坊，磨坊主以每袋 $p$ 金币的价格售卖面粉。游戏中还有一座酒馆，酒保以每袋 $q$ 金币（$q > p$）的价格收购面粉。显然堡堡可以赚取其中的差价，但在两处地点之间移动，以及点击购买和卖出的按钮都需要时间。

更精确地，如果堡堡一次性从磨坊购买了 $x$ 袋面粉，需要花 $(ax + b)$ 秒以及 $px$ 金币；如果堡堡一次性向酒馆卖出了 $x$ 袋面粉，需要花 $(cx + d)$ 秒，但能赚取 $qx$ 金币。堡堡现在有 $m$ 金币，但因为堡堡马上就要上床睡觉了，他最多只能再玩 $t$ 秒游戏。求堡堡打完游戏时最多能持有多少金币。

输入格式

有多组测试数据。第一行输入一个整数 $T$（$1 \le T \le 500$）表示测试数据组数，对于每组测试数据：

第一行输入三个整数 $p$，$a$ 和 $b$（$1 \le p, a \le 10^9$，$0 \le b \le 10^9$）。

第二行输入三个整数 $q$，$c$ 和 $d$（$p < q \le 10^9$，$1 \le c \le 10^9$，$0 \le d \le 10^9$）。

第三行输入两个整数 $m$ 和 $t$（$1 \le m, t \le 10^9$）。

输出格式

每组数据输出一行一个整数，表示堡堡经过至多 $t$ 秒后最多能持有多少金币。

3
5 2 3
8 1 5
14 36
5 2 0
8 1 3
17 6
100 1 0
10000 1 0
99 100000

32
20
99

提示

对于第一组样例数据，一种最优方案是：

• 堡堡首先从磨坊购买 $2$ 袋面粉，花费 $2 \times 2 + 3 = 7$ 秒以及 $5 \times 2 = 10$ 金币。然后他把所有面粉卖给酒馆，花费 $1 \times 2 + 5 = 7$ 秒但赚取了 $8 \times 2 = 16$ 金币。堡堡现在有 $14 - 10 + 16 = 20$ 金币，还剩 $36 - 7 - 7 = 22$ 秒。
• 堡堡接下来从磨坊购买 $4$ 袋面粉，花费 $2 \times 4 + 3 = 11$ 秒以及 $5 \times 4 = 20$ 金币。然后他把所有面粉卖给酒馆，花费 $1 \times 4 + 5 = 9$ 秒但赚取了 $8 \times 4 = 32$ 金币。堡堡现在有 $20 - 20 + 32 = 32$ 金币，还剩 $22 - 11 - 9 = 2$ 秒。
• 现在堡堡没有时间买卖面粉了。所以答案是 $32$。

对于第二组样例数据，堡堡只有时间买卖一袋面粉。所以答案是 $17 - 5 + 8 = 20$。

对于第三组样例数据，堡堡没有足够的金币购买面粉。所以答案是 $99$。