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. [Image] 

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. [Image] 

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


-----Input-----

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

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


-----Example-----
Input
2
-3 1
1 3 5 7 9 11
1000000000 1000000000
1000000000 1000000000 1000000000 1000000000 1000000000 1000000000

Output
18
1000000000000000000



-----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$. [Image]

Difficulty: interview

Starter code:

Solutions:
import sys
input = sys.stdin.readline

def main():
    x, y = list(map(int, input().split()))
    clst = list(map(int, input().split()))
    clst[0] = min(clst[0], clst[5] + clst[1])
    clst[1] = min(clst[1], clst[0] + clst[2])
    clst[2] = min(clst[2], clst[1] + clst[3])
    clst[3] = min(clst[3], clst[2] + clst[4])
    clst[4] = min(clst[4], clst[3] + clst[5])
    clst[5] = min(clst[5], clst[4] + clst[0])
    directions = [(1, 1), (0, 1), (-1, 0), (-1, -1), (0, -1), (1, 0)]
    ans = 10 ** 20
    for i in range(6):
        dx1, dy1 = directions[i]
        dx2, dy2 = directions[(i + 1) % 6]
        a = (x * dy2 - y * dx2) // (dx1 * dy2 - dy1 * dx2)
        b = (x * dy1 - y * dx1) // (dx2 * dy1 - dy2 * dx1)
        if a < 0 or b < 0:
            continue
        ans = min(ans, clst[i] * a + clst[(i + 1) % 6] * b)
    print(ans)
    
for _ in range(int(input())):
    main()


def read_int():
    return int(input())


def read_ints():
    return list(map(int, input().split(' ')))


d = [(1, 1), (0, 1), (-1, 0), (-1, -1), (0, -1), (1, 0)]
t = read_int()
for case_num in range(t):
    x, y = read_ints()
    c = list(read_ints())
    ans = -1
    for i in range(6):
        dx = d[i][0]
        dy = d[i][1]
        if dx != 0 and x // dx >= 0:
            t = x // dx
            cost = t * c[i]
            y1 = d[i][1] * t
            for j in range(6):
                if j == i or d[j][0] != 0:
                    continue
                t1 = (y - y1) // d[j][1]
                if t1 >= 0:
                    nc = cost + t1 * c[j]
                    if ans == -1 or ans > nc:
                        ans = nc

        if dy != 0 and y // dy >= 0:
            t = y // dy
            cost = t * c[i]
            x1 = d[i][0] * t
            for j in range(6):
                if j == i or d[j][1] != 0:
                    continue
                t1 = (x - x1) // d[j][0]
                if t1 >= 0:
                    nc = cost + t1 * c[j]
                    if ans == -1 or ans > nc:
                        ans = nc
    print(ans)


import sys
input = sys.stdin.readline
for f in range(int(input())):
    x,y=map(int,input().split())
    c1,c2,c3,c4,c5,c6=map(int,input().split())
    c2=min(c2,c1+c3)
    c5=min(c5,c4+c6)
    c6=min(c6,c1+c5)
    c3=min(c3,c2+c4)
    
    c1=min(c1,c2+c6)
    c4=min(c4,c3+c5)
    if x*y>0:
        if x>0:
            d=min(x,y)
            x-=d
            y-=d
            print(x*c6+y*c2+d*c1)
        else:
            x=-x
            y=-y
            d=min(x,y)
            x-=d
            y-=d
            print(x*c3+y*c5+d*c4)
    else:
        cost=0
        if x>0:
            cost+=x*c6
        else:
            cost-=x*c3
        if y>0:
            cost+=y*c2
        else:
            cost-=y*c5
        print(cost)

t = int(input())

for _ in range(t):
    x0, y0 = input().split()
    x0, y0 = int(x0), int(y0)

    c = [0] + list(map(int, input().split())) 
    c[0] = c[-1]
    c.append(c[1])

    for i in range(1, 7):
        c[i] = min(c[i], c[i-1] + c[i+1])

    c[7] = c[1]
    
    s = (None, [1, 1], [0, 1], [-1, 0], [-1, -1], [0, -1], [1, 0], [1, 1])

    ans = 1e30
    for i in range(1, 7):
        x1, y1 = s[i]
        x2, y2 = s[i+1]

        a = (x0*y2 - y0*x2)//(x1*y2 - y1*x2)
        b = (x0*y1 - y0*x1)//(x2*y1 - y2*x1)
        
        if (a >= 0) and (b >= 0):
            ans = min(ans, a*c[i] + b*c[i+1])

    print(ans)
        


import io
import os
import sys
import math
import heapq


input = sys.stdin.readline
mod = 10**9 + 7
 
t = int(input())


for _ in range(t):
    x,y = list(map(int, input().split()))
    arr = list(map(int, input().split()))
    arr = arr + arr + arr
    
    for z in range(20):
        for i in range(1,16):
            arr[i] = min(arr[i], arr[i-1] + arr[i+1])
            
    c1,c2,c3,c4,c5,c6 = (arr[6:12])
    if x>=0 and y>=0:
        ans = 0
        mm = min(x,y)
        x -= mm
        y -= mm
        ans += mm * c1
        ans += y*c2
        ans += x*c6
        print(ans)
    elif x>=0 and y<0:
        ans = 0
        ans += abs(y)*c5
        ans += x*c6
        print(ans)
    elif x<0 and y<0:
        ans = 0
        x,y = abs(x),abs(y)
        mm = min(x,y)
        x -= mm
        y -= mm
        ans += mm * c4
        ans += y*c5
        ans += x*c3
        print(ans)
    else:
        ans = 0
        ans += abs(y) * c2
        ans += abs(x) * c3
        print(ans)

gans = []
for _ in range(int(input())):
    y, x = list(map(int, input().split()))
    c2, c3, c4, c5, c6, c1 = list(map(int, input().split()))
    for i in range(6):
        c1 = min(c1, c6 + c2)
        c2 = min(c2, c1 + c3)
        c3 = min(c3, c2 + c4)
        c4 = min(c4, c3 + c5)
        c5 = min(c5, c4 + c6)
        c6 = min(c6, c5 + c1)
    if x == 0 and y == 0:
        gans.append(0)
        continue
    elif x == 0:
        if y > 0:
            ans = y * c1
        else:
            ans = -y * c4
        gans.append(ans)
        continue
    elif y == 0:
        if x > 0:
            ans = x * c3
        else:
            ans = -x * c6
        gans.append(ans)
        continue
    if x * y > 0:
        if x > 0:
            a, b, c = c1, c2, c3
        else:
            a, b, c = c4, c5, c6
            x = -x
            y = -y
        ans = min(x, y) * b
        if x > y:
            ans += (x - y) * c
        else:
            ans += (y - x) * a
        gans.append(ans)
    else:
        if x < 0:
            ans = -c6 * x + c1 * y
        else:
            ans = -c4 * y + c3 * x
        gans.append(ans)
print('\n'.join(map(str, gans)))
        
        
        


T = int(input())

for t in range(T):
    X, Y = [int(_) for _ in input().split()]
    C = [int(_) for _ in input().split()]

    for _ in range(10):
        for i in range(len(C)):
            prev = i-1
            if prev < 0:
                prev += 6
            nxt = i+1
            if nxt >= 6:
                nxt -= 6
            C[i] = min(C[i], C[prev]+C[nxt])
        for i in range(len(C)-1, -1, -1):
            prev = i-1
            if prev < 0:
                prev += 6
            nxt = i+1
            if nxt >= 6:
                nxt -= 6
            C[i] = min(C[i], C[prev]+C[nxt])

    c1, c2, c3, c4, c5, c6 = C[0], C[1], C[2], C[3], C[4], C[5]

    if X == 0:
        if Y > 0:
            print(c2 * Y)
        else:
            print(c5 * abs(Y))
    elif X < 0:
        if Y >= 0:
            print(c3 * abs(X) + c2 * Y)
        elif Y <= X:
            print(c4 * abs(X) + c5 * abs(X-Y))
        else:
            print(c3 * abs(X-Y) + c4 * abs(Y))
    elif X > 0:
        if Y >= X:
            print(c1 * X + (Y-X) * c2)
        elif Y <= 0:
            print(c6 * X + abs(Y) * c5)
        else:
            print(c1 * Y + c6 * (X-Y))


import heapq


def dijkstra(g: list, start, goal=None):
    num = len(g)          # グラフのノード数
    dist = [float('inf') for i in range(num)]
    dist[start] = 0
    q = []
    heapq.heappush(q, (0, start))  # 始点をpush
    while q:
        prov_cost, src = heapq.heappop(q)  # pop
        if dist[src] < prov_cost:
            continue
        for node, cost in g[src]:
            if dist[node] > dist[src] + cost:
                dist[node] = dist[src] + cost
                heapq.heappush(q, (dist[node], node))
    return dist


dxdy = ((1, 1), (0, 1), (-1, 0), (-1, -1), (0, -1), (1, 0))
INF = 3 * 10 ** 18
t = int(input())
for _ in range(t):
    x, y = list(map(int, input().split()))
    c = list(map(int, input().split()))
    g = [[] for _ in range(25)]
    for i in range(5):
        for j in range(5):
            for k in range(6):
                dx, dy = dxdy[k]
                if 0 <= i + dx < 5 and 0 <= j + dy < 5:
                    g[i * 5 + j].append(((i + dx) * 5 + j + dy, c[k]))
    dist = dijkstra(g, 12)
    for i in range(6):
        dx, dy = dxdy[i]
        c[i] = dist[12 + dx * 5 + dy]
    ans = 0
    if x > 0 and y > 0:
        m = min(x, y)
        ans += m * c[0]
        x -= m
        y -= m
    elif x < 0 and y < 0:
        m = max(x, y)
        ans -= m * c[3]
        x -= m
        y -= m
    if x > 0:
        ans += x * c[5]
    else:
        ans -= x * c[2]
    if y > 0:
        ans += y * c[1]
    else:
        ans -= y * c[4]
    print(ans)


for nt in range(int(input())):
	y,x = list(map(int,input().split()))
	c1,c2,c3,c4,c5,c6 = list(map(int,input().split()))
	for i in range(10):
		c2 = min(c2,c1+c3)
		c3 = min(c3,c2+c4)
		c4 = min(c4,c3+c5)
		c5 = min(c5,c4+c6)
		c6 = min(c6,c5+c1)
		c1 = min(c1,c6+c2)
	# print (c1,c2,c3,c4,c5,c6)
	if x>=0:
		if y>=0:
			m = min(x,y)
			x -= m
			y -= m
			print(m*c1+c2*x+c6*y)
		else:
			y = abs(y)
			print(x*c2+y*c3)
	else:
		x = abs(x)
		if y>=0:
			print(x*c5+y*c6)
		else:
			y = abs(y)
			m = min(x,y)
			x -= m
			y -= m
			print(m*c4+x*c5+y*c3)


# import sys; input = sys.stdin.buffer.readline
# sys.setrecursionlimit(10**7)
from collections import defaultdict
mod = 10 ** 9 + 7; INF = float("inf")

def getlist():
	return list(map(int, input().split()))

def inverse(N, mod):
	return (pow(N, mod - 2, mod))

def main():
	T = int(input())
	for _ in range(T):
		x, y = getlist()
		C = getlist()
		D = [INF] * 8
		D[0] = min(C[5], C[0] + C[4])
		D[1] = min(C[0], C[1] + C[5])
		D[2] = min(C[1], C[0] + C[2])
		D[3] = min(C[1] + C[2], C[0] + 2 * C[2], C[3] + 2 * C[1])
		D[4] = min(C[2], C[1] + C[3])
		D[5] = min(C[3], C[2] + C[4])
		D[6] = min(C[4], C[3] + C[5])
		D[7] = min(C[4] + C[5], C[3] + 2 * C[5], C[0] + 2 * C[4])
		if x >= 0 and y >= 0:
			m = min(x, y)
			ans = D[1] * m + D[0] * (x - m) + D[2] * (y - m)
		elif x >= 0 and y < 0:
			m = min(x, -y)
			ans = D[7] * m + D[0] * (x - m) + D[6] * (-y - m)
		elif x < 0 and y >= 0:
			m = min(-x, y)
			ans = D[3] * m + D[4] * (-x - m) + D[2] * (y - m)
		 # x, y < 0
		else:
			m = min(-x, -y)
			ans = D[5] * m + D[4] * (-x - m) + D[6] * (-y - m)
		print(ans)


def __starting_point():
	main()
__starting_point()

from bisect import bisect_left as bl
from bisect import bisect_right as br
from heapq import heappush,heappop
import math
from collections import *
from functools import reduce,cmp_to_key
import sys
input = sys.stdin.readline
M = mod = 998244353
def factors(n):return sorted(set(reduce(list.__add__, ([i, n//i] for i in range(1, int(n**0.5) + 1) if n % i == 0))))
def inv_mod(n):return pow(n, mod - 2, mod)
 
def li():return [int(i) for i in input().rstrip('\n').split()]
def st():return input().rstrip('\n')
def val():return int(input().rstrip('\n'))
def li2():return [i for i in input().rstrip('\n')]
def li3():return [int(i) for i in input().rstrip('\n')]

for _ in range(val()):
    x, y = li()
    c1, c2, c3, c4, c5, c6 = li()

    for i in range(30):
        c1 = min(c1, c2 + c6)
        c6 = min(c6, c1 + c5)
        c5 = min(c5, c6 + c4)
        c4 = min(c4, c5 + c3)
        c2 = min(c2, c1 + c3)
        c3 = min(c3, c2 + c4)

    temp = min(abs(x), abs(y))

    if x >= 0 and y >= 0:
        x -= temp
        y -= temp

        ans = temp * c1 + x * c6 + y * c2

    elif x <= 0 and y >= 0:
        x = abs(x)
        ans = x * c3 + y * c2

    elif x >= 0 and y <= 0:
        y = abs(y)

        ans = x * c6 + y * c5

    else:
        x += temp
        y += temp
        x = abs(x)
        y = abs(y)

        ans = temp * c4 + x * c3 + y * c5


    print(ans)


def xyc(x, y):
    an1 = 0
    if x > 0:
        an1 += cos[5] * x
    else:
        an1 += cos[2] * (-x)
    if y > 0:
        an1 += cos[1] * y
    else:
        an1 += cos[4] * (-y)
    # print(an1)
    return an1


t = int(input())
for _ in range(t):
    p = list(map(int, input().split()))
    x, y = p[0], p[1]
    cos = list(map(int, input().split()))
    for a in range(len(cos)):
        if cos[(a + 1) % 6] + cos[(a - 1) % 6] < (cos[a]):
            cos[a] = cos[(a + 1) % 6] + cos[(a - 1) % 6]
    # print(cos)
    an1 = xyc(x, y)
    an2 = 0
    if x * y < 0:
        an2 = an1
    else:
        if (x > 0) and (x > y):
            an2 += cos[0] * (y)
            an2 += xyc(x - y, 0)
        elif x > 0:
            an2 += cos[0] * x
            an2 += xyc(0, y - x)
        elif (x < 0) and (x < y):
            an2 += cos[3] * (-y)
            an2 += xyc(x - y, 0)
        else:
            an2 += cos[3] * (-x)
            an2 += xyc(0, y - x)

    print(min(an1, an2))


import sys
input=sys.stdin.readline

T=int(input())
for _ in range(T):
    n,m=list(map(int,input().split()))
    c1,c2,c3,c4,c5,c6=list(map(int,input().split()))
    c1=min(c1,c2+c6)
    c2=min(c2,c1+c3)
    c3=min(c3,c2+c4)
    c4=min(c4,c3+c5)
    c5=min(c5,c4+c6)
    c6=min(c6,c5+c1)


    ans=0
    if (m>0):
        if (n<=0):
            ans=(c3*(-n))+(c2*m)

        else:
            if (n<=m):
                ans=(c1*n)+(c2*(m-n))
            else:
                ans=(c1*m)+(c6*(n-m))

    elif(m<0):
        if (n<=0):
            if (n<=m):
                ans=(c4*(-m))+(c3*(-n+m))
            else:
                ans=c4*(-n)+c5*(n-m)
        else:
            ans=(c6*n)+(c5*(-m))
    else:
        if (n<=0):
            ans=c3*(-n)
        else:
            ans=c6*n
    print(ans)


n = int(input())
for _ in range(n):
    y, x = list(map(int, input().split()))
    costs = list(map(int, input().split()))
    for i in range(36):
        costs[i % 6] = min(costs[i % 6], costs[(i+5) % 6] + costs[(i+1) % 6])
    ans = 0
    if x >= 0:
        if y >= 0:
            if x >= y:
                # 1
                ans = (x-y) * costs[1] + y * costs[0]
            else:
                # 2
                ans = x * costs[0] + (y-x) * costs[5]
        else:
            # 6
            ans = x * costs[1] - y * costs[2]
    else:
        if y >= 0:
            # 3
            ans = -x * costs[4] + y * costs[5]
        else:
            if x <= y:
                # 4
                ans = (y-x) * costs[4] - y * costs[3]
            else:
                # 5
                ans = (-x) * costs[3] + (x-y) * costs[2]
    print(ans)


import sys

def input(): return sys.stdin.readline().strip()
def list2d(a, b, c): return [[c for j in range(b)] for i in range(a)]
def list3d(a, b, c, d): return [[[d for k in range(c)] for j in range(b)] for i in range(a)]
def list4d(a, b, c, d, e): return [[[[e for l in range(d)] for k in range(c)] for j in range(b)] for i in range(a)]
def ceil(x, y=1): return int(-(-x // y))
def INT(): return int(input())
def MAP(): return list(map(int, input().split()))
def LIST(N=None): return list(MAP()) if N is None else [INT() for i in range(N)]
def Yes(): print('Yes')
def No(): print('No')
def YES(): print('YES')
def NO(): print('NO')
INF = 10**19
MOD = 10**9 + 7
EPS = 10**-10

for _ in range(INT()):
    gy, gx = MAP()
    C = LIST()

    C[5] = min(C[5], C[0]+C[4])
    C[1] = min(C[1], C[0]+C[2])
    C[2] = min(C[2], C[3]+C[1])
    C[4] = min(C[4], C[3]+C[5])
    C[5] = min(C[5], C[0]+C[4])
    C[1] = min(C[1], C[0]+C[2])
    C[2] = min(C[2], C[3]+C[1])
    C[4] = min(C[4], C[3]+C[5])

    ans = 0
    if gx > 0 and gy > 0:
        mn = min(gx, gy)
        ans += mn * min(C[1]+C[5], C[0])
        if gx > gy:
            ans += (gx-mn) * C[1]
        elif gx < gy:
            ans += (gy-mn) * C[5]
    elif gx < 0 and gy < 0:
        gx, gy = abs(gx), abs(gy)
        mn = min(gx, gy)
        ans += mn * min(C[2]+C[4], C[3])
        if gx > gy:
            ans += (gx-mn) * C[4]
        elif gx < gy:
            ans += (gy-mn) * C[2]
    else:
        if gx < 0:
            ans += abs(gx) * C[4]
        elif gx > 0:
            ans += gx * C[1]
        if gy < 0:
            ans += abs(gy) * C[2]
        elif gy > 0:
            ans += gy * C[5]
    print(ans)


import sys
input = sys.stdin.readline

t = int(input())
for i in range(t):
    x,y = map(int,input().split())
    lis = list(map(int,input().split()))
    costs = [0]*6
    costs[0] = min(lis[0],lis[1]+lis[5])
    costs[1] = min(lis[1],lis[0]+lis[2])
    costs[2] = min(lis[2],lis[1]+lis[3])
    costs[3] = min(lis[3],lis[2]+lis[4])
    costs[4] = min(lis[4],lis[3]+lis[5])
    costs[5] = min(lis[5],lis[4]+lis[0])
    ans = 0
    if x >= 0 and y >= 0:
        ans += min(x,y) * costs[0]
        if x >= y:
            ans += (x-y) * costs[5]
        else:
            ans += (y-x) * costs[1]
    elif x <= 0 and y <= 0:
        ans += min(abs(x),abs(y)) * costs[3]
        if x <= y:
            ans += (y-x) * costs[2]
        else:
            ans += (x-y) * costs[4]
    elif x >= 0 and y <= 0:
        ans += x*costs[5]
        ans += abs(y)*costs[4]
    elif x <= 0 and y >= 0:
        ans += abs(x)*costs[2]
        ans += abs(y)*costs[1]
    print(ans)

import sys, math
import io, os
#data = io.BytesIO(os.read(0,os.fstat(0).st_size)).readline
from bisect import bisect_left as bl, bisect_right as br, insort
from heapq import heapify, heappush, heappop
from collections import defaultdict as dd, deque, Counter
#from itertools import permutations,combinations
def data(): return sys.stdin.readline().strip()
def mdata(): return list(map(int, data().split()))
def outl(var) : sys.stdout.write('\n'.join(map(str, var))+'\n')
def out(var) : sys.stdout.write(str(var)+'\n')
#from decimal import Decimal
#from fractions import Fraction
#sys.setrecursionlimit(100000)
INF = float('inf')
mod=10**9+7


for t in range(int(data())):
    y,x=mdata()
    c=mdata()
    if x>=0 and y>=0:
        out(min(c[1]*x+c[5]*y,c[0]*min(x,y)+c[1]*(x-min(x,y))+c[5]*(y-min(x,y)),c[0]*max(x,y)+c[4]*(max(x,y)-x)+c[2]*(max(x,y)-y)))
    elif x>0 and y<0:
        y=abs(y)
        out(min(c[1] * x + c[2] * y,c[0]*x+c[2]*(x+y),c[3]*y+c[1]*(x+y)))
    elif x<0 and y>0:
        x=abs(x)
        out(min(c[4] * x + c[5] * y,c[3]*x+c[5]*(x+y),c[0]*y+c[4]*(x+y)))
    else:
        x=abs(x)
        y=abs(y)
        out(min(c[4] * x + c[2] * y, c[3] * min(x, y) + c[4] * (x - min(x, y)) + c[2] * (y - min(x, y)),
                c[3] * max(x, y) + c[1] * (max(x, y) - x) + c[5] * (max(x, y) - y)))

def func(x, c2, c5):
    if x < 0:
        return -x * c5
    else:
        return x * c2
def func_2(x, c4, c1):
    if x < 0:
        return -x*c4
    else:
        return x*c1

def func_3(x, c6, c3):
    if x < 0:
        return -x*c3
    else:
        return x * c6

def main():
    y, x = map(int, input().split())
    c1, c2, c3, c4, c5, c6 = map(int, input().split())
    lu = (1,0)
    ru = (1,1)
    rd = (-1,0)
    r = (0, 1)
    l = (1, 0)
    ld = (-1, -1)
    a= func_3(y, c6, c3) + func(x, c2, c5)
    b =func_2(y, c4, c1) + func(x - y, c2, c5)
    c = func_2(x, c4, c1) + func_3(y - x, c6, c3)
    print(min(a,b,c))



def __starting_point():
    t = int(input())
    for i in range(t):
        main()
"""
123
1232
123232
23232123232
d(abc)e
ad(abc)e
Ad(abc)eC
dabe
adbeb
ebdadbeb
bebdadbeb
acccc
accccc
caccccc
ccccacaccccc
cccccacaccccc
"""
__starting_point()