Lindsey Buckingham 告诉 Stevie Nicks“走你自己的路”。尼克斯现在很伤心,想尽快离开,但她生活在一个二维的六边形世界里。
考虑平面的六边形平铺,如下图所示。
Nicks 希望从标记为 $$$(0, 0)$$$ 的单元格转到坐标给出的某个单元格。她可以从六边形移动到您想要的六个邻居中的任何一个,但是每个六边形都有相关的成本。费用仅取决于您旅行的方向。从 $$$(0, 0)$$$ 到 $$$(1, 1)$$$ 的成本与从 $$$(-2, -1)$$$ 到 $$$(-1, 0)$$$ 的成本完全相同。输入中的成本按 $$$c_1$$$、$$$c_2$$$、$$$c_3$$$、$$$c_4$$$、$$$c_5$$$、$$$c_6$$$ 的顺序给出,如下图所示。
打印从坐标为 $$$(0, 0)$$$ 的原点到给定单元格的最小路径成本。
输入
每个测试包含多个测试用例。第一行包含测试用例的数量 $$$t$$$ ($$$1 \le t \le 10^{4}$$$)。测试用例的描述如下。
每个测试用例的第一行包含两个整数 $$$x$$$ 和 $$$y$$$ ($$$-10^{9} \le x, y \le 10^{9}$$$) 表示目标六边形的坐标。
每个测试用例的第二行包含六个整数 $$$c_1$$$, $$$c_2$$$, $$$c_3$$$, $$$c_4$$$, $$$c_5$$$, $$$c_6$$$ ($$$1 \le c_1, c_2, c_3, c_4, c_5, c_6 \le 10^{9}$$$) 代表在特定方向上迈出一步的六种成本(请参阅上图查看每个值对应哪条边)。
输出
对于每个测试用例,输出从原点到给定单元格的路径的最小成本。
示例
输入 #1
2 -3 1 1 3 5 7 9 11 1000000000 1000000000 1000000000 1000000000 1000000000 1000000000 1000000000 1000000000
输出 #1
18 1000000000000000000
注意
下图显示了第一个示例的解决方案。通过$$$c_3$$$ 3次和$$$c_2$$$一次达到成本$$$18$$$,总计$$$5+5+5+3=18$$$。