Read problems statements in Mandarin chinese, Russian andVietnamese as well. 

Chef lives in the Universe in which only planets are present. Every planet is identified by 3 integers [p, q, r]. Chef lives on the planet [0, 0, 0] and wants to go to planet [X, Y, Z] with minimum energy loss.

The energy loss is determined by the following rules:

If Chef goes from [p, q, r] to [p+1, q, r] or [p, q+1, r] or [p, q, r+1], then A units of energy are lost.
If Chef goes from [p, q, r] to [p+1, q+1, r] or [p, q+1, r+1] or [p+1, q, r+1], then B units of energy are lost.
If Chef goes from [p, q, r] to [p+1, q+1, r+1], then C units of energy are lost.

Your task is to calculate the minimum energy loss possible when Chef goes from planet [0, 0, 0] to planet [X, Y, Z].

------ Input ------ 

The first line of the input contains a single integer T denoting the number of test cases. The description of T test cases follows.
The only line of each test case contains 6 space-separated integers denoting the values of X, Y, Z, A, B and C respectively.

------ Output ------ 

For each test case, output a single line containing one integer — the minimum energy loss.

------ Constraints ------ 

$1 ≤  T  ≤ 10^{5}$ 
$1 ≤ X, Y, Z ≤ 10^{5}$ 
$1 ≤ A, B, C ≤ 10^{3}$ 

------ Subtasks ------ 

Subtask #1 (20 points):

$1 ≤ T ≤ 50$ 
$1 ≤ X, Y, Z ≤ 100$ 

Subtask #2 (80 points): original constraints

----- Sample Input 1 ------ 
2
1 2 3 10 1 5
2 2 1 1 2 3
----- Sample Output 1 ------ 
3
5
----- explanation 1 ------ 
Example case 1: One of the possible solutions is [0, 0, 0] -->  [1, 0, 1]  -->  [1, 1, 2]  -->  [1, 2, 3]. The minimum energy loss is B + B + B = 3 · B = 3 · 1 = 3.
Example case 2: One of the possible solutions is [0, 0, 0] -->  [1, 1, 1]  -->  [2, 2, 1]. The minimum energy loss is C + B = 3 + 2 = 5.

Difficulty: HARD
Tags: Constructive algorithms

Ad-hoc

Starter code:

Solutions:
t = int(input())
for i in range(t):
	(x, y, z, a, b, c) = list(map(int, input().strip().split(' ')))
	ans = 10 ** 18
	(x, y, z) = sorted([x, y, z])
	ans = min(ans, (x + y + z) * a)
	if (x + y + z) % 2 == 0 and x + y >= z:
		ans = min(ans, (x + y + z) // 2 * b)
	if x == y and y == z:
		ans = min(ans, x * c)
	if x + y < z:
		ans = min(ans, (x + y) * b + (z - x - y) * a)
	elif (x + y + z) % 2 == 1:
		ans = min(ans, a + (x + y + z) // 2 * b)
	ans = min(ans, x * c + (y + z - 2 * x) * a)
	if (x + y + z) % 2 != 0 and x + y > z:
		ans = min(ans, c + (x + y + z - 3) // 2 * b)
	common = min(x, z - y)
	if a + c <= 2 * b:
		ans = min(ans, common * (a + c) + (x - common) * c + (z - y - common) * a + (y - x) * b)
	else:
		ans = min(ans, common * (2 * b) + (x - common) * c + (z - y - common) * a + (y - x) * b)
	print(int(ans))


for t in range(int(input())):
	(x, y, z, a, b, c) = map(int, input().split())
	addition = x + y + z
	maximum = max(x, y, z)
	minimum = min(x, y, z)
	if 3 * a <= 1.5 * b:
		if 3 * a <= c:
			print(addition * a)
			continue
		else:
			price = minimum * c + (addition - 3 * minimum) * a
			print(price)
			continue
	elif 1.5 * b <= c:
		if 3 * a <= c:
			if addition - maximum >= maximum:
				z = maximum + (addition - 2 * maximum) // 2
				f = addition - 2 * z
				c2 = z * b + f * a
			else:
				z = addition - maximum
				f = addition - 2 * z
				c2 = z * b + f * a
			print(c2)
			continue
		else:
			if addition - maximum >= maximum:
				z = maximum + (addition - 2 * maximum) // 2
				f = addition - 2 * z
				c2 = f * c + (z - f) * b
				c3 = z * b + f * a
				if c3 < c2:
					c2 = c3
			else:
				z = addition - maximum
				f = addition - 2 * z
				c2 = z * b + f * a
			print(c2)
			continue
	elif addition - maximum >= maximum:
		z = minimum
		f = addition - maximum - z * 2
		g = addition - 2 * f - 3 * z
		c3 = z * c + f * b + g * a
		f = 3 * maximum - addition
		z = addition - 2 * maximum
		price = z * c + f * b
		print(min(price, c3))
		continue
	else:
		z = minimum
		f = addition - maximum - z * 2
		g = addition - 2 * f - 3 * z
		c3 = z * c + f * b + g * a
		z = addition - maximum
		f = addition - 2 * z
		c2 = z * b + f * a
		print(min(c2, c3))


from sys import stdin
T = 1
T = int(stdin.readline().strip())
for _ in range(T):
	(x, y, z, a, b, c) = map(int, stdin.readline().split())
	small = min(x, y, z)
	big = max(x, y, z)
	big2 = x + y + z - (big + small)
	mini = small
	ans = []
	sm = small + big2 + big
	if 2 * a > b:
		if big2 + mini < big:
			localans = (big2 + mini) * b + (big - big2 - mini) * a
		elif sm % 2 == 0:
			localans = int(sm / 2 * b)
		else:
			localans = int((sm - 1) / 2 * b + a)
	else:
		localans = sm * a
	ans.append(localans)
	if small >= 1 and big2 >= 1 and (big >= 1):
		localans = c
		small1 = small - 1
		big1 = big - 1
		big21 = big2 - 1
		sm = small1 + big1 + big21
		if 2 * a > b:
			if big21 + small1 < big:
				localans += (big21 + small1) * b + (big1 - big21 - small1) * a
			elif sm % 2 == 0:
				localans += int(sm / 2 * b)
			else:
				localans += int((sm - 1) / 2 * b + a)
		else:
			localans += sm * a
		ans.append(localans)
	localans = c * small
	small1 = 0
	big21 = big2 - small
	big1 = big - small
	sm = small1 + big21 + big1
	if 2 * a > b:
		if big21 + small1 < big:
			localans += (big21 + small1) * b + (big1 - big21 - small1) * a
		elif sm % 2 == 0:
			localans += int(sm / 2 * b)
		else:
			localans += int((sm - 1) / 2 * b + a)
	else:
		localans += sm * a
	ans.append(localans)
	if big2 + small > big:
		var = abs(big - small - big2)
		localans = var * c
		small1 = small - var
		big21 = big2 - var
		big1 = big - var
		sm = small1 + big21 + big1
		if 2 * a > b:
			if big21 + small1 < big:
				localans += (big21 + small1) * b + (big1 - big21 - small1) * a
			elif sm % 2 == 0:
				localans += int(sm / 2 * b)
			else:
				localans += int((sm - 1) / 2 * b + a)
		else:
			localans += sm * a
		ans.append(localans)
	finalans = min(ans)
	print(finalans)


def find(dubli, other, a, b, c, flag):
	count = 0
	if flag == 1:
		b = 2 * a
	elif flag == 2:
		c = 3 * a
	if dubli > other:
		diff = dubli - other
		count += diff * b
		if 2 * c <= 3 * b:
			count += other * c
		elif other % 2 == 0:
			x = other // 2
			x *= 3
			count += x * b
		else:
			x = other - 1
			x = x // 2
			x *= 3
			count += min(x * b + c, x * b + b + a)
	elif other > 2 * dubli:
		count = min(2 * dubli * b + (other - 2 * dubli) * a, dubli * c + (other - dubli) * a)
	else:
		x = 2 * (other - dubli)
		y = other - x
		l = x * b
		if 2 * c <= 3 * b:
			l += y * c
		elif y % 2 == 0:
			y = y // 2
			y *= 3
			l += y * b
		else:
			y = y - 1
			y = y // 2
			y *= 3
			l += min(y * b + c, y * b + b + a)
		m = 0
		m += dubli * c + (other - dubli) * a
		count += min(l, m)
	return count
t = int(input())
for i in range(t):
	(x, y, z, a, b, c) = map(int, input().split())
	min1 = 0
	midd = 0
	max1 = 0
	max1 = max(x, y)
	max1 = max(max1, z)
	min1 = min(x, y)
	min1 = min(min1, z)
	midd = x + y + z - min1 - max1
	count = 0
	d = 0
	x = 0
	other = 0
	if 2 * a <= b and 3 * a <= c:
		print((max1 + midd + min1) * a)
	elif b >= 2 * a and c <= 3 * a:
		count += (midd - min1) * b
		m2 = max1
		m2 = m2 - (midd - min1)
		count += find(min1, m2, a, b, c, 1)
		print(min(count, min1 * c + (midd - min1 + max1 - min1) * a))
	elif b <= 2 * a and c > 3 * a:
		count += (midd - min1) * b
		m2 = max1
		m2 = m2 - (midd - min1)
		count += find(min1, m2, a, b, c, 2)
		print(min(count, min1 * b + (midd - min1) * b + (max1 - (midd - min1)) * a))
	elif b <= 2 * a and c <= 3 * a:
		if max1 == min1 and max1 == midd:
			if 2 * c <= 3 * b:
				print(c * max1)
			elif max1 % 2 == 0:
				x = max1 // 2
				x *= 3
				print(b * x)
			else:
				x = max1 - 1
				x = x // 2
				x *= 3
				print(min(b * x + c, b * x + b + a))
		elif max1 == midd or max1 == min1 or min1 == midd:
			if max1 == midd:
				d = max1
				other = min1
			elif max1 == min1:
				d = max1
				other = midd
			else:
				d = midd
				other = max1
			print(find(d, other, a, b, c, 0))
		else:
			l = 0
			l += (midd - min1) * b
			m2 = max1
			max1 = max1 - (midd - min1)
			l += find(min1, max1, a, b, c, 0)
			m = 0
			m += min1 * c + (midd - min1) * b + (m2 - midd) * a
			print(min(l, m))


for t in range(int(input())):
	(x, y, z, a, b, c) = map(int, input().split())
	sum1 = x + y + z
	max1 = max(x, y, z)
	min1 = min(x, y, z)
	if 3 * a <= 1.5 * b:
		if 3 * a <= c:
			print(sum1 * a)
			continue
		else:
			cost = min1 * c + (sum1 - 3 * min1) * a
			print(cost)
			continue
	elif 1.5 * b <= c:
		if 3 * a <= c:
			if sum1 - max1 >= max1:
				e = max1 + (sum1 - 2 * max1) // 2
				f = sum1 - 2 * e
				c2 = e * b + f * a
			else:
				e = sum1 - max1
				f = sum1 - 2 * e
				c2 = e * b + f * a
			print(c2)
			continue
		else:
			if sum1 - max1 >= max1:
				e = max1 + (sum1 - 2 * max1) // 2
				f = sum1 - 2 * e
				c2 = f * c + (e - f) * b
				c3 = e * b + f * a
				if c3 < c2:
					c2 = c3
			else:
				e = sum1 - max1
				f = sum1 - 2 * e
				c2 = e * b + f * a
			print(c2)
			continue
	elif sum1 - max1 >= max1:
		e = min1
		f = sum1 - max1 - e * 2
		g = sum1 - 2 * f - 3 * e
		c3 = e * c + f * b + g * a
		f = 3 * max1 - sum1
		e = sum1 - 2 * max1
		cost = e * c + f * b
		print(min(cost, c3))
		continue
	else:
		e = min1
		f = sum1 - max1 - e * 2
		g = sum1 - 2 * f - 3 * e
		c3 = e * c + f * b + g * a
		e = sum1 - max1
		f = sum1 - 2 * e
		c2 = e * b + f * a
		print(min(c2, c3))


import sys
f = sys.stdin
t = int(f.readline())
for i in range(t):
	(x, y, z, a, b, c) = map(int, f.readline().split())
	if 2 * a <= b and 3 * a <= c:
		print((x + y + z) * a)
	elif 2 * a <= b and 3 * a >= c:
		mi = min(x, y, z)
		tb = mi * c
		x -= mi
		y -= mi
		z -= mi
		tb += (x + y + z) * a
		print(tb)
	elif b <= 2 * a and c >= 3 * a:
		n1 = min(x, y, z)
		n3 = max(x, y, z)
		n2 = x + y + z - n1 - n3
		tb2 = (n2 - n1) * b
		n3 -= n2 - n1
		n2 -= n2 - n1
		if n3 <= 2 * n1:
			while n1 != n2 or n1 != n3 or n2 != n3:
				if n1 != 0 and n2 != 0 and (n3 != 0):
					z = n3 - n1
					if z % 2 != 0:
						z += 1
					n3 -= z
					tb2 += z * b
					z = z // 2
					n2 -= z
					n1 -= z
				else:
					tb2 += n2 * b
					tb2 += (n3 - n2) * a
					(n1, n2, n3) = (0, 0, 0)
		else:
			n3 -= 2 * n1
			tb2 += 2 * n1 * b
			tb2 += n3 * a
			(n1, n2, n3) = (0, 0, 0)
		if n1 % 2 != 0:
			z = min(c, b + a, 3 * a)
			tb2 += z
			n1 -= 1
		z = min(2 * b + 2 * a, b + c + a, 3 * b, b + 4 * a, 2 * c, c + 3 * a, 6 * a)
		tb2 += n1 // 2 * z
		print(tb2)
	else:
		n1 = min(x, y, z)
		n3 = max(x, y, z)
		n2 = x + y + z - n1 - n3
		ans = n1 * c
		n2 -= n1
		n3 -= n1
		ans += n2 * b
		n3 -= n2
		ans += n3 * a
		n1 = min(x, y, z)
		n3 = max(x, y, z)
		n2 = x + y + z - n1 - n3
		tb2 = (n2 - n1) * b
		n3 -= n2 - n1
		n2 -= n2 - n1
		if n3 <= 2 * n1:
			while n1 != n2 or n1 != n3 or n2 != n3:
				if n1 != 0 and n2 != 0 and (n3 != 0):
					z = n3 - n1
					if z % 2 != 0:
						z += 1
					n3 -= z
					tb2 += z * b
					z = z // 2
					n2 -= z
					n1 -= z
				else:
					tb2 += n2 * b
					tb2 += (n3 - n2) * a
					(n1, n2, n3) = (0, 0, 0)
		else:
			n3 -= 2 * n1
			tb2 += 2 * n1 * b
			tb2 += n3 * a
			(n1, n2, n3) = (0, 0, 0)
		if n1 % 2 != 0:
			z = min(c, b + a, 3 * a)
			tb2 += z
			n1 -= 1
		z = min(2 * b + 2 * a, b + c + a, 3 * b, b + 4 * a, 2 * c, c + 3 * a, 6 * a)
		tb2 += n1 // 2 * z
		print(min(ans, tb2))


t = int(input())
for i in range(t):
	(x, y, z, a, b, c) = map(int, input().split())
	cost = [[6 * a, 1], [3 * b, 2], [2 * c, 3]]
	cost.sort()
	(x, y, z) = sorted([x, y, z])
	if cost[0][1] == 1:
		s = x + y + z
		ans = s * a
	elif cost[1][1] == 1:
		if cost[0][1] == 2:
			(lx, ly, lz) = (x, y, z)
			count = 0
			count += ly - lx
			lz -= count
			ly -= count
			diff = lz - lx
			if diff > lx:
				count += 2 * lx
				lz -= 2 * lx
				lx = 0
				ly = 0
			else:
				count += 2 * diff
				lx = lx - diff
				ly = lx
				lz = lx
				count += 3 * (lx // 2)
				lx = 0
				ly = 0
				if lz % 2 == 0:
					lz = 0
				else:
					count += 1
					lz = 1
			ans = count * b + lz * a
		else:
			s = x + y + z
			ans = x * c + (s - 3 * x) * a
	else:
		(lx, ly, lz) = (x, y, z)
		count = 0
		count += ly - lx
		lz -= count
		ly -= count
		diff = lz - lx
		if diff > lx:
			count += 2 * lx
			lz -= 2 * lx
			lx = 0
			ly = 0
		else:
			count += 2 * diff
			lx = lx - diff
			ly = lx
			lz = lx
			count += 3 * (lx // 2)
			lx = 0
			ly = 0
			if lz % 2 == 0:
				lz = 0
			else:
				count += 1
				lz = 1
		ans = count * b + lz * a
		if x > 0 and y > 0 and (z > 0):
			(lx, ly, lz) = (x - 1, y - 1, z - 1)
			count = 0
			count += ly - lx
			lz -= count
			ly -= count
			diff = lz - lx
			if diff > lx:
				count += 2 * lx
				lz -= 2 * lx
				lx = 0
				ly = 0
			else:
				count += 2 * diff
				lx = lx - diff
				ly = lx
				lz = lx
				count += 3 * (lx // 2)
				lx = 0
				ly = 0
				if lz % 2 == 0:
					lz = 0
				else:
					count += 1
					lz = 1
			ans1 = count * b + lz * a + c
			ans = min(ans, ans1)
		ans1 = x * c + (y - x) * b
		cd = 2 * b - c
		if cd < a:
			if z - y > x:
				ans1 += x * cd + (z - y - x) * a
			else:
				ans1 += (z - y) * cd
		else:
			ans1 += (z - y) * a
		ans = min(ans, ans1)
	print(ans)


from math import inf
T = int(input())
for _ in range(T):
	(X, Y, Z, A, B, C) = [int(x) for x in input().split()]
	(X, Y, Z) = sorted([X, Y, Z], reverse=True)
	valueOrder = ''.join([i[1] for i in sorted([(6 * A, 'A'), (3 * B, 'B'), (2 * C, 'C')])])
	(singles, doubles, triples) = (0, 0, 0)
	if valueOrder == 'ABC' or valueOrder == 'ACB':
		singles += X + Y + Z
		X = 0
		Y = 0
		Z = 0
	elif valueOrder == 'BAC':
		if X >= Y + Z:
			doubles = Y + Z
			X -= doubles
			Y = 0
			Z = 0
			singles += X
			X -= singles
		elif X < Y + Z:
			if (X + Y + Z) % 2 == 1:
				X -= 1
				singles += 1
				(X, Y, Z) = sorted([X, Y, Z], reverse=True)
			doubles += (X + Y + Z) // 2
			X = 0
			Y = 0
			Z = 0
	elif valueOrder == 'BCA':
		if (X + Y + Z) % 2 == 0 and X < Y + Z:
			doubles += (X + Y + Z) // 2
			X = 0
			Y = 0
			Z = 0
		elif (X + Y + Z) % 2 == 1 and X < Y + Z:
			if C <= B + A:
				doubles += (X + Y + Z - 3) // 2
				(X, Y, Z) = (1, 1, 1)
				triples += 1
				X -= 1
				Y -= 1
				Z -= 1
			else:
				doubles += (X + Y + Z - 1) // 2
				(X, Y, Z) = (1, 0, 0)
				singles += 1
				X -= 1
		elif X >= Y + Z:
			doubles += Y + Z
			X -= Y + Z
			Y = 0
			Z = 0
			singles += X
			X = 0
	elif valueOrder == 'CAB':
		triples += Z
		X -= triples
		Y -= triples
		Z -= triples
		singles += X + Y
		X = 0
		Y = 0
	elif valueOrder == 'CBA':
		if X >= Y + Z:
			if A + C >= 2 * B:
				doubles += Y + Z
				X -= doubles
				Y = 0
				Z = 0
				singles += X
				X -= singles
			else:
				triples += Z
				X -= triples
				Y -= triples
				Z -= triples
				doubles += Y
				X -= doubles
				Y -= doubles
				singles += X
				X -= singles
		elif X < Y + Z:
			(X_A, Y_A, Z_A) = (X, Y, Z)
			(singles, doubles, triples) = (0, 0, 0)
			triples += Z_A
			X_A -= triples
			Y_A -= triples
			Z_A -= triples
			doubles += Y_A
			X_A -= doubles
			Y_A -= doubles
			singles += X_A
			X_A -= singles
			energyA = C * triples + B * doubles + A * singles
			(X_B, Y_B, Z_B) = (X, Y, Z)
			(singles, doubles, triples) = (0, 0, 0)
			triples += Y_B + Z_B - X_B
			X_B -= triples
			Y_B -= triples
			Z_B -= triples
			doubles += (X_B + Y_B + Z_B) // 2
			energyB = C * triples + B * doubles + A * singles
			print(min(energyA, energyB))
			continue
	energyUsed = C * triples + B * doubles + A * singles
	print(energyUsed)


T = int(input())
for case in range(T):
	(X, Y, Z, A, B, C) = [int(val) for val in input().split()]
	if 2 * A <= B and 3 * A <= C:
		print(A * (X + Y + Z))
		continue
	(X, Y, Z) = sorted([X, Y, Z])
	if B <= 2 * A and 3 * B <= 2 * C:
		if Z > X + Y:
			print(A * (Z - X - Y) + B * (X + Y))
			continue
		elif X + Y + Z & 1 and A + B > C:
			print(B * ((X + Y + Z) // 2 - 1) + C)
			continue
		else:
			print(B * ((X + Y + Z) // 2) + A * (X + Y + Z & 1))
			continue
	elif 2 * A <= B:
		print(C * X + A * (Y + Z - 2 * X))
		continue
	elif 2 * B < A + C:
		if Z > X + Y:
			print(A * (Z - X - Y) + B * (X + Y))
			continue
		else:
			ones = Z - Y
			pairs = min(ones, X)
			print(B * (2 * pairs + Y - X) + A * (ones - pairs) + C * (X - pairs))
			continue
	else:
		print(C * X + B * (Y - X) + A * (Z - Y))
		continue


for iiiiiiiiiiiiiiii in range(int(input())):
	(x, y, z, a, b, c) = map(int, input().strip().split(' '))
	aa = [x, y, z]
	aa.sort()
	x = aa[0]
	y = aa[1]
	z = aa[2]
	n = x
	m = y - x
	o = z - y
	cost = min(3 * b, 2 * c, 2 * b + 2 * a, 6 * a, b + 4 * a)
	ans1 = o * a + m * min(2 * a, b)
	if n % 2 == 1:
		ans1 += min(c, 3 * a, b + a)
	ans1 = ans1 + cost * (n // 2)
	ans2 = 0
	t = min(n, o)
	n -= t
	o -= t
	m += 2 * t
	ans2 = o * a + m * min(2 * a, b)
	if n % 2 == 1:
		ans2 += min(c, 3 * a, b + a)
	ans2 = ans2 + cost * (n // 2)
	print(min(ans1, ans2))


t = int(input())
for i in range(t):
	x = [-1, -1, -1]
	(x[0], x[1], x[2], a, b, c) = map(int, input().split())
	x.sort(reverse=True)
	b = min(b, 2 * a)
	c = min(c, 3 * a)
	c = min(c, b + a)
	na = x[0] - x[1]
	nb = x[1] - x[2]
	nc = x[2]
	NA = na
	NB = nb
	NC = nc
	cost1 = 0
	cost2 = 0
	if c + a > 2 * b:
		temp = min(nc, na)
		nc -= temp
		na -= temp
		nb += 2 * temp
	if 3 * b < 2 * c:
		nb += 3 * (nc // 2)
		nc = nc % 2
	cost1 = na * a + nb * b + nc * c
	na = NA
	nb = NB
	nc = NC
	if 3 * b < 2 * c:
		nb += 3 * (nc // 2)
		nc = nc % 2
	if c + a > 2 * b:
		temp = min(nc, na)
		nc -= temp
		na -= temp
		nb += 2 * temp
	cost2 = na * a + nb * b + nc * c
	print(min(cost1, cost2))


t = int(input())
for _ in range(t):
	(x_, y_, z_, a, b, c) = map(int, input().split())
	s = x_ + y_ + z_
	x = min(x_, y_, z_)
	z = max(x_, y_, z_)
	y = s - x - z
	if b >= a + a:
		if c < a + a + a:
			e = x * c + (y - x + z - x) * a
		else:
			e = s * a
	elif c + a < b + b:
		e = x * c + (y - x) * b + (z - y) * a
	elif c + c < b + b + b:
		if x + y <= z:
			e = (x + y) * b + (z - x - y) * a
		else:
			d = x + y - z
			e = d * c + (z - d) * b
	else:
		if x + y <= z:
			e0 = (x + y) * b + (z - x - y) * a
		else:
			e0 = s // 2 * b + s % 2 * a
		if x == 0:
			e1 = e0
		elif x - 1 + y - 1 <= z - 1:
			e1 = c + (x - 1 + y - 1) * b + (z - 1 - x + 1 - y + 1) * a
		else:
			e1 = c + (s - 3) // 2 * b + (s - 3) % 2 * a
		e = min(e1, e0)
	print(e)


def solve1(x, a, b, c):
	if 3 * b >= 2 * c:
		return x * c
	return x // 2 * (3 * b) + x % 2 * c

def solve2(x, z, a, b, c):
	if x == z:
		return solve1(x, a, b, c)
	if x == 0:
		return a * z
	ret = 0
	if z > 2 * x:
		ret = (z - 2 * x) * a
		z = 2 * x
	if a + c <= 2 * b:
		return ret + c * x + a * (z - x)
	q = min(x, z - x)
	ret += (z - x) * 2 * b
	return ret + solve1(2 * x - z, a, b, c)

def solve(x, y, z, a, b, c):
	(x, y, z) = sorted([x, y, z])
	b = min(b, 2 * a)
	c = min(c, a + b)
	if b >= a * 2:
		return (z + y - 2 * x) * a + solve1(x, a, b, c)
	elif x == y:
		return solve2(x, z, a, b, c)
	else:
		return (y - x) * b + solve2(x, z - (y - x), a, b, c)
import sys
f = sys.stdin
t = int(f.readline())
for i in range(t):
	z = list(map(int, f.readline().split()))
	print(solve(*z))