王国英雄

题目描述

《王国英雄》是一款点击式冒险游戏，游戏中的主角踏上了拯救父亲的危险旅程，并成为了王国的英雄。

游戏中的钱叫做金币，可以用来购买各种用品，甚至完成某些任务。俗话说，富贵险中求，我们的天才玩家BaoBao就找到了一条致富之路。游戏中有一个磨坊，磨坊主以每袋 $p$ 金币的价格出售面粉。还有一家酒馆，酒保以每袋 $q$ 金币（ $q > p$ ）的价格购买面粉。显然，BaoBao可以将差价收入囊中，但在两个地方之间移动和点击买卖按钮也需要时间。

更确切地说，如果BaoBao一次从磨坊买入 $x$ 袋面粉，他需要花费 $(ax + b)$ 秒和 $px$ 金币；如果BaoBao一次从酒馆卖出 $x$ 袋面粉，他需要花费 $(cx + d)$ 秒，但可以赚取 $qx$ 金币。BaoBao目前有 $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$ 秒之后，BaoBao可以拥有的最大金子数量。

样例 #1

样例输入 #1

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

样例输出 #1

32
20
99

提示

对于第一个示例测试用例，最佳策略之一是

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

在第二个样本测试用例中，BaoBao只来得及买一袋面粉和卖一袋面粉。因此答案为 $17 - 5 + 8 = 20$ 。

第三个测试案例中，BaoBao没有足够的金币购买面粉。所以答案是 $99$ 。