← 返回题目列表

Codeforces · 1421/D

D. 六边形

中文机器翻译题面 查看原题

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$$$。