Hexagons
Contest: Codeforces Round 676 (Div. 2)
Difficulty rating: 1900
Tags: brute force, constructive algorithms, greedy, implementation, math, shortest paths

Lindsey Buckingham told Stevie Nicks "Go your own way". Nicks is now sad and wants to go away as quickly as possible, but she lives in a 2D hexagonal world.

Consider a hexagonal tiling of the plane as on the picture below.

Nicks wishes to go from the cell marked $$$(0, 0)$$$ to a certain cell given by the coordinates. She may go from a hexagon to any of its six neighbors you want, but there is a cost associated with each of them. The costs depend only on the direction in which you travel. Going from $$$(0, 0)$$$ to $$$(1, 1)$$$ will take the exact same cost as going from $$$(-2, -1)$$$ to $$$(-1, 0)$$$. The costs are given in the input in the order $$$c_1$$$, $$$c_2$$$, $$$c_3$$$, $$$c_4$$$, $$$c_5$$$, $$$c_6$$$ as in the picture below.

Print the smallest cost of a path from the origin which has coordinates $$$(0, 0)$$$ to the given cell.

Input format:
Each test contains multiple test cases. The first line contains the number of test cases $$$t$$$ ($$$1 \le t \le 10^{4}$$$). Description of the test cases follows.

The first line of each test case contains two integers $$$x$$$ and $$$y$$$ ($$$-10^{9} \le x, y \le 10^{9}$$$) representing the coordinates of the target hexagon.

The second line of each test case contains six integers $$$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}$$$) representing the six costs of the making one step in a particular direction (refer to the picture above to see which edge is for each value).

Output format:
For each testcase output the smallest cost of a path from the origin to the given cell.

Constraints:
Time limit: 2.0 s
Memory limit: 256.0 MB

Note:
The picture below shows the solution for the first sample. The cost $$$18$$$ is reached by taking $$$c_3$$$ 3 times and $$$c_2$$$ once, amounting to $$$5+5+5+3=18$$$.

Example input:
2
-3 1
1 3 5 7 9 11
1000000000 1000000000
1000000000 1000000000 1000000000 1000000000 1000000000 1000000000

Example output:
18
1000000000000000000

Editorial:
Hint:
Using too many edges in the solution feels wasteful, the solution surely has some neat line as straight as possible. Perhaps we can prove only two edges are required?
Solution:
Indeed two edges are required in the solution, so one approach would be picking all combinations of edges and do linear algebra so see how many times each is required (or if it's impossible).
To prove that let's suppose our target is somewhere reachable by only taking C1 and C2 (the upper right sextant, a sixth division of the plane). C4 and C5 will never be used since they contribute in the wrong direction. We can now use C6, C1, C2 or C3 for our solution. If using C1 and C2 is not optimal we can choose C3 or C6, without loss of generality we choose C3. C6 cannot be used because it simply counters C3. Now we either use C1, C2 or C3, but we can further narrow down to just two edges. If we use all three this means we use C1+C3 which goes the same way as C2, and C2 also goes the same way as C1+C3. So we can just not use C2 if C1+C3 < C2, or use C2 instead of C1+C3 until either of C1 or C3 doesn't appear anymore on our solution.