Migrated from Lutece 1275 喵哈哈的宝藏

All parts of this problem, including description, images, samples, data and checker, might be broken. If you find bugs in this problem, please contact the admins.

Description

沈宝宝和廖巨巨在玩一个挖宝藏游戏：游戏地图是一个二维平面，廖巨巨一开始站在$(0,0)$位置，面向$X$轴正方向。

游戏开始前廖巨巨就已经知道宝藏落在左下角为$(X_1,Y_1)$，右上角为$(X_2,Y_2)$的一个矩形内。更准确地说，宝藏的位置$(X,Y)$满足$X_1 \leq X \leq X_2$,$Y_1 \leq Y \leq Y_2$，且$X$和$Y$为整数。保证矩形包含点$(0,0)$。

廖巨巨可以购买五种卡片：

1. 转向卡-转到$X$正方向，每张卡片$A$块钱。
2. 转向卡-转到$X$负方向，每张卡片$B$块钱。
3. 转向卡-转到$Y$正方向，每张卡片$C$块钱。
4. 转向卡-转到$Y$负方向，每张卡片$D$块钱。
5. 移动卡-向前走$K$步，其中$K$为任意廖巨巨想要的正整数，但只能在游戏开始之前确定这个数字，游戏开始后不能改变这个数字，一步对应坐标系上的一个单位，每张卡片$E$块钱。

每种卡片都可以购买任意张或不买，在使用一次后都会消失。游戏开始后不能再购买卡片。

游戏开始后，沈宝宝会告诉廖巨巨宝藏的位置$(X,Y)$，廖巨巨需要通过使用卡片恰好移动到宝藏的位置。

当廖巨巨恰好移动到宝藏的位置时，廖巨巨就获得了胜利，否则就视为失败。

那么现在问题来了，廖巨巨至少要用多少块钱，才能必胜。必胜即对于任何一个可能的$(X,Y)$，廖巨巨都能胜利。

作为看客的何老师早就知道了答案，你知道吗？

Input

第一行有$1$个整数$T$，$1 \leq T \leq 1000$，表示测试数据数量。

接下来有$T$行：

每行有$9$个整数，$A$,$B$,$C$,$D$,$E$,$X_1$,$Y_1$,$X_2$,$Y_2$，保证$1 \leq A,B,C,D,E \leq 1000$,$-1000000 \leq X_1, Y_1 \leq 0$,$0 \leq X_2,Y_2 \leq 1000000$

Output

对于每个样例输出一行，包含一个整数，表示廖巨巨的最少花费。

Samples

3
1 1 1 1 1 -2 0 3 0
1 100 1 1 1 -2 0 3 0
1 1 1 1 1 -1 -1 1 1

3
102
5

Note

对于第一组样例：

可以带一张『转向卡-转到Y负方向』、一张『移动卡-向前走1步』和一张『移动卡-向前走2步』。
若宝藏落在(0,0)，不需要使用卡片。
若宝藏落在(1,0)，使用『移动卡-向前走1步』。
若宝藏落在(2,0)，使用『移动卡-向前走2步』。
若宝藏落在(3,0)，使用『移动卡-向前走1步』『移动卡-向前走1步』。
若宝藏落在(-1,0)，使用『转向卡-转到Y负方向』『移动卡-向前走1步』。
若宝藏落在(-2,0)，使用『转向卡-转到Y负方向』『移动卡-向前走2步』。
总共花费3块钱。

对于第二组样例：

与第一组类似

对于第三组样例：

廖巨巨可以带一张『转向卡-转到X负方向』、一张『转向卡-转到Y正方向』、一张『转向卡-转到Y负方向』、两张『移动卡-向前走1步』。

by Hezhu

Resources

每周一题