Read problem statements in [Bengali], [Mandarin Chinese], [Russian], and [Vietnamese] as well.

Chef and $N-1$ more of his friends go to the night canteen. The canteen serves only three items (well, they serve more, but only these three are edible!), which are omelette, chocolate milkshake, and chocolate cake. Their prices are $A$, $B$ and $C$ respectively.

However, the canteen is about to run out of some ingredients. In particular, they only have $E$ eggs and $H$ chocolate bars left. They need:
$2$ eggs to make an omelette
$3$ chocolate bars for a chocolate milkshake
$1$ egg and $1$ chocolate bar for a chocolate cake

Each of the $N$ friends wants to order one item. They can only place an order if the canteen has enough ingredients to prepare all the ordered items. Find the smallest possible total price they have to pay or determine that it is impossible to prepare $N$ items.

------  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 first and only line of each test case contains six space-separated integers $N$, $E$, $H$, $A$, $B$ and $C$.

------  Output ------
For each test case, print a single line containing one integer ― the minimum cost of $N$ items, or $-1$ if it is impossible to prepare $N$ items.

------  Constraints ------
$1 ≤ T ≤ 2 \cdot 10^{5}$
$1 ≤ N ≤ 10^{6}$
$0 ≤ E, H ≤ 10^{6}$
$1 ≤ A, B, C ≤ 10^{6}$
the sum of $N$ over all test cases does not exceed $10^{6}$

------  Subtasks ------
Subtask #1 (30 points): $1 ≤ N ≤ 100$

Subtask #2 (70 points): original constraints

----- Sample Input 1 ------ 
3

5 4 4 2 2 2

4 5 5 1 2 3

4 5 5 3 2 1
----- Sample Output 1 ------ 
-1

7

4
----- explanation 1 ------ 
Example case 1: The maximum number of items that can be produced using $4$ eggs and $4$ chocolates is $4$, so the answer is $-1$.

Example case 2: In the optimal solution, the friends should order $2$ omelettes, $1$ chocolate milkshake and $1$ chocolate cake, with cost $1 \cdot 2 + 2 \cdot 1 + 3 \cdot 1 = 7$.

Example case 3: In the optimal solution, the friends should order $4$ chocolate cakes, with cost $1 \cdot 4 = 4$.

Difficulty: MEDIUM_HARD
Tags: Constructive algorithms

Implementation

Complete search

Mathematics

Ad-hoc
Skill types: Complete search

Starter code:

Solutions:
from math import inf
for __ in range(int(input())):
	(n, e, h, a, b, c) = map(int, input().split())
	min_cost = inf
	for chocolate_cake in range(min(n, min(e, h)) + 1):
		total_cost = chocolate_cake * c
		remaining = n - chocolate_cake
		egg = max(0, e - chocolate_cake)
		choco_bar = max(0, h - chocolate_cake)
		if a < b:
			total_cost += min(egg // 2, remaining) * a
			remaining -= min(egg // 2, remaining)
			total_cost += min(choco_bar // 3, remaining) * b
			remaining -= min(choco_bar // 3, remaining)
		else:
			total_cost += min(choco_bar // 3, remaining) * b
			remaining -= min(choco_bar // 3, remaining)
			total_cost += min(egg // 2, remaining) * a
			remaining -= min(egg // 2, remaining)
		if not remaining:
			min_cost = min(min_cost, total_cost)
	if min_cost == inf:
		print(-1)
	else:
		print(min_cost)


t = int(input())
for i in range(t):
	(n, e, h, a, b, c) = map(int, input().split())
	l2 = []
	ans = 1e+18
	for j in range(n + 1):
		if j > e or j > h:
			break
		m1 = (e - j) // 2
		m2 = (h - j) // 3
		if n > j + m1 + m2:
			continue
		if a < b:
			r1 = min(n - j, m1)
			r2 = n - j - r1
		else:
			r2 = min(n - j, m2)
			r1 = n - j - r2
		p = j * c + r1 * a + r2 * b
		ans = min(ans, p)
	if ans == 1e+18:
		print(-1)
	else:
		print(ans)


for _ in range(int(input())):
	(n, e, h, a, b, c) = map(int, input().split())
	l2 = []
	ans = 1e+18
	for numc in range(n + 1):
		if numc > e or numc > h:
			break
		maxo = (e - numc) // 2
		maxm = (h - numc) // 3
		if n > numc + maxo + maxm:
			continue
		if a < b:
			reqo = min(n - numc, maxo)
			reqm = n - numc - reqo
		else:
			reqm = min(n - numc, maxm)
			reqo = n - numc - reqm
		price = numc * c + reqo * a + reqm * b
		ans = min(ans, price)
	if ans == 1e+18:
		print(-1)
	else:
		print(ans)


T = int(input())
for t in range(T):
	(N, Eggs, Chocos, OC, MC, CC) = map(int, input().split())
	ans = 1e+18
	for cakes in range(N + 1):
		if Eggs < cakes or Chocos < cakes:
			break
		omelette = int((Eggs - cakes) / 2)
		milkshake = int((Chocos - cakes) / 3)
		if cakes + milkshake + omelette < N:
			continue
		if OC < MC:
			reqomelette = min(omelette, N - cakes)
			reqmilkshake = N - cakes - reqomelette
		else:
			reqmilkshake = min(milkshake, N - cakes)
			reqomelette = N - cakes - reqmilkshake
		price = cakes * CC + reqmilkshake * MC + reqomelette * OC
		ans = min(ans, price)
	if ans == 1e+18:
		ans = -1
	print(ans)


inf = 10 ** 20
for _ in range(int(input())):
	(n, e, h, a, b, c) = list(map(int, input().split()))
	ans = inf
	for num_cake in range(min(e, h, n) + 1):
		max_oml = max(0, (e - num_cake) // 2)
		max_bar = max(0, (h - num_cake) // 3)
		if num_cake + max_oml + max_bar >= n:
			price = 0
			price += num_cake * c
			item_left = n - num_cake
			if a == b:
				price += a * item_left
			elif a > b:
				bar_count = min(item_left, max_bar)
				price += bar_count * b
				item_left -= bar_count
				if item_left > 0:
					price += item_left * a
			else:
				oml_count = min(item_left, max_oml)
				price += oml_count * a
				item_left -= oml_count
				if item_left > 0:
					price += item_left * b
			ans = min(ans, price)
	if ans >= inf:
		print(-1)
	else:
		print(ans)


try:
	for i in range(int(input())):
		(n, e, h, a, b, c) = map(int, input().split())
		ans = 1e+18
		for i in range(n + 1):
			if e < i or h < i:
				break
			mo = (e - i) // 2
			mc = (h - i) // 3
			if n > mo + mc + i:
				continue
			if a > b:
				rc = min(n - i, mc)
				ro = n - i - rc
			else:
				ro = min(n - i, mo)
				rc = n - i - ro
			p = ro * a + rc * b + i * c
			ans = min(p, ans)
		if ans == 1e+18:
			print('-1')
		else:
			print(ans)
except:
	pass


import math

def unc(n, e, h, a, b, c):
	res = math.inf
	for noc in range(0, n + 1):
		if e < noc or h < noc:
			break
		maxO = (e - noc) // 2
		maxChoc = (h - noc) // 3
		if noc + maxChoc + maxO < n:
			continue
		if a < b:
			noO = min(n - noc, maxO)
			noChoc = n - noc - noO
		else:
			noChoc = min(n - noc, maxChoc)
			noO = n - noc - noChoc
		res = min(res, a * noO + b * noChoc + c * noc)
	if res == math.inf:
		return -1
	return res
for _ in range(int(input())):
	(n, e, h, a, b, c) = list(map(int, input().split()))
	print(unc(n, e, h, a, b, c))


ip = int(input())
while ip:
	(N, E, H, A, B, C) = [int(i) for i in input().split(' ')]
	best_cost = float('inf')
	for cakes in range(N + 1):
		Egg = E - cakes
		Choc = H - cakes
		if Egg < 0 or Choc < 0:
			continue
		omlette = Egg // 2
		shakes = Choc // 3
		if omlette + shakes + cakes < N:
			continue
		total_cost = 0
		NUM = N - cakes
		if A <= B:
			total_cost += cakes * C
			omlette_req = min(NUM, omlette)
			total_cost += A * omlette_req
			NUM = NUM - omlette_req
			total_cost += B * NUM
			best_cost = min(best_cost, total_cost)
		else:
			total_cost += cakes * C
			milkshake_req = min(NUM, shakes)
			total_cost += B * milkshake_req
			NUM = NUM - milkshake_req
			total_cost += A * NUM
			best_cost = min(best_cost, total_cost)
	if best_cost == float('inf'):
		print('-1')
	else:
		print(best_cost)
	ip -= 1


for _ in range(int(input())):
	(n, egg, choc, a, b, c) = map(int, input().split())
	best = float('inf')
	for i in range(n + 1):
		E = egg - i
		CH = choc - i
		if E < 0 or CH < 0:
			continue
		(om, shk) = (E // 2, CH // 3)
		if i + om + shk < n:
			continue
		num = n - i
		cost = 0
		if a <= b:
			cost += i * c
			m = min(num, om)
			cost += m * a
			num -= m
			m = min(shk, num)
			cost += m * b
			best = min(best, cost)
		else:
			cost += i * c
			m = min(num, shk)
			cost += m * b
			num -= m
			m = min(om, num)
			cost += m * a
			best = min(best, cost)
	if best == float('inf'):
		print('-1')
	else:
		print(best)


import sys

def get_ints():
	return map(int, sys.stdin.readline().strip().split())
sys.setrecursionlimit(1500000)
t = int(input())

def dfs(n, e, h, a, b, c):
	if n < 0:
		return 0
	ans = 10 ** 15
	if 2 * n <= e:
		ans = min(ans, n * a)
	if n <= e and n <= h:
		ans = min(ans, n * c)
	if 3 * n <= h:
		ans = min(ans, b * n)
	if (h - n) // 2 >= 1 and (h - n) // 2 >= n - e:
		if b - c < 0:
			k = min(n - 1, (h - n) // 2)
		else:
			k = max(n - e, 1)
		ans = min(ans, (b - c) * k + n * c)
	if e - n >= 1 and e - n >= n - h:
		if a - c < 0:
			k = min(n - 1, e - n)
		else:
			k = max(n - h, 1)
		ans = min(ans, (a - c) * k + n * c)
	if e // 2 >= 1 and e // 2 + h // 3 >= n:
		if a < b:
			k = min(n - 1, e // 2)
		else:
			k = max((3 * n - h + 2) // 3, 1)
		ans = min(ans, (a - b) * k + n * b)
	if e >= 3 and h >= 4 and (n >= 3):
		ans = min(ans, a + b + c + dfs(n - 3, e - 3, h - 4, a, b, c))
	return ans
for i in range(0, t):
	(n, e, h, a, b, c) = get_ints()
	final = dfs(n, e, h, a, b, c)
	if final == 10 ** 15:
		final = -1
	print(final)


def min_cost(N, E, H, A, B, C):
	res = 1e+18
	for cake in range(N + 1):
		if E < cake or H < cake:
			break
		maxO = (E - cake) // 2
		maxM = (h - cake) // 3
		if cake + maxO + maxM < N:
			continue
		else:
			if A < B:
				reqO = min(N - cake, maxO)
				reqM = N - cake - reqO
			else:
				reqM = min(N - cake, maxM)
				reqO = N - cake - reqM
			price = cake * C + A * reqO + B * reqM
			res = min(res, price)
	return res if res != 1e+18 else -1
T = int(input())
for _ in range(T):
	(n, e, h, a, b, c) = map(int, input().split())
	ans = min_cost(n, e, h, a, b, c)
	print(ans)


import sys
sys.setrecursionlimit(10 ** 6)

def fa(n, e, h, a, b, c):
	ans = 10 ** 13
	if n <= e and n <= h:
		ans = min(ans, n * c)
	if 2 * n <= e:
		ans = min(ans, n * a)
	if n * 3 <= h:
		ans = min(ans, n * b)
	if (h - n) // 2 >= 1 and (h - n) // 2 >= n - e:
		if b - c < 0:
			k = min(n - 1, (h - n) // 2)
			ans = min(ans, (b - c) * k + n * c)
		else:
			k = max(1, n - e)
			ans = min(ans, (b - c) * k + n * c)
	if e - n >= 1 and e - n >= n - h:
		if a - c < 0:
			k = min(n - 1, e - n)
			ans = min(ans, (a - c) * k + n * c)
		else:
			k = max(1, n - h)
			ans = min(ans, (a - c) * k + n * c)
	if e // 2 >= 1 and e // 2 >= (3 * n - h + 2) // 3:
		if a - b < 0:
			k = min(n - 1, e // 2)
			ans = min(ans, (a - b) * k + n * b)
		else:
			k = max(1, (3 * n - h + 2) // 3)
			ans = min(ans, (a - b) * k + n * b)
	if e >= 3 and h >= 4 and (n >= 3):
		ans = min(ans, a + b + c + fa(n - 3, e - 3, h - 4, a, b, c))
	return ans
for i in range(int(input())):
	(n, e, h, a, b, c) = list(map(int, input().split()))
	ans = 10 ** 10
	if n <= 0:
		print(0)
	else:
		P = fa(n, e, h, a, b, c)
		if P == 10 ** 13:
			print(-1)
		else:
			print(P)


import math
T = int(input())
for z in range(T):
	(N, E, H, A, B, C) = map(int, input().split(' '))
	mini = -1
	for a in range(0, N + 1):
		c_max = min(N - a, E - 2 * a)
		c_min = max(math.ceil((3 * N - 3 * a - H) / 2), 0)
		b_min = N - a - c_max
		b_max = min(N - a, N - a - c_min)
		if c_min > c_max or b_min > b_max or c_max < 0 or (b_max < 0):
			continue
		if B < C:
			price = a * A + b_max * B + (N - a - b_max) * C
		else:
			price = a * A + (N - a - c_max) * B + c_max * C
		if mini != -1:
			mini = min(mini, price)
		else:
			mini = price
	print(mini)


T = int(input())
for i in range(T):
	(N, E, H, A, B, C) = (int(x) for x in input().split())
	l = []
	if N > E and N > H:
		print('-1')
	else:
		for cake in range(0, min(N, min(E, H)) + 1):
			if E - cake >= 0 and H - cake >= 0:
				o = (E - cake) // 2
				s = (H - cake) // 3
				if A <= B:
					omletes = min(N - cake, o)
					shake = N - cake - omletes
					if s >= shake and omletes >= 0 and (shake >= 0):
						price = cake * C + omletes * A + shake * B
						l.append(price)
				else:
					shake = min(N - cake, s)
					omletes = N - cake - shake
					if o >= omletes and omletes >= 0 and (shake >= 0):
						price = cake * C + omletes * A + shake * B
						l.append(price)
		if len(l) == 0:
			print('-1')
		else:
			print(min(l))


from sys import stdin, stdout
(readline, writeline) = (stdin.readline, stdout.write)
for _ in range(int(readline())):
	(n, egg, choc, a, b, c) = map(int, readline().split())
	best = float('inf')
	for i in range(n + 1):
		E = egg - i
		CH = choc - i
		if E < 0 or CH < 0:
			continue
		(om, shk) = (E // 2, CH // 3)
		if i + om + shk < n:
			continue
		num = n - i
		cost = 0
		if a <= b:
			cost += i * c
			m = min(num, om)
			cost += m * a
			num -= m
			m = min(shk, num)
			cost += m * b
			best = min(best, cost)
		else:
			cost += i * c
			m = min(num, shk)
			cost += m * b
			num -= m
			m = min(om, num)
			cost += m * a
			best = min(best, cost)
	if best == float('inf'):
		print('-1')
	else:
		print(best)


t = int(input())
for i in range(t):
	(n, e, h, a, b, c) = map(int, input().split())
	ans = 1e+18
	for cake in range(0, n + 1):
		if e < cake or h < cake:
			break
		omlets = (e - cake) // 2
		milkshake = (h - cake) // 3
		if cake + omlets + milkshake < n:
			continue
		if a < b:
			reqomletes = min(n - cake, omlets)
			reqmilkshake = n - cake - reqomletes
		else:
			reqmilkshake = min(n - cake, milkshake)
			reqomletes = n - cake - reqmilkshake
		price = cake * c + reqomletes * a + reqmilkshake * b
		ans = min(ans, price)
	if ans == 1e+18:
		print(-1)
	else:
		print(ans)


from operator import itemgetter
from math import floor

def solution(N, E, H, A, B, C):
	imp_cost = max(A, B, C) * (N + 5)
	min_cost = imp_cost
	for z in range(N + 1):
		if E < z or H < z:
			continue
		maxX = min(N - z, floor((E - z) / 2))
		maxY = min(N - z, floor((H - z) / 3))
		if z + maxX + maxY < N:
			continue
		if A < B:
			x = maxX
			y = N - z - x
		else:
			y = maxY
			x = N - z - y
		cost = A * x + B * y + C * z
		if cost < min_cost:
			min_cost = cost
	if min_cost == imp_cost:
		min_cost = -1
	return min_cost

def main():
	T = int(input())
	for t in range(T):
		(N, E, H, A, B, C) = [int(x) for x in input().split()]
		print(solution(N, E, H, A, B, C))
main()


t = int(input())
for l in range(t):
	(n, e, h, a, b, c) = map(int, input().split())
	if a < b:
		s = True
	else:
		s = False
	ans = 1e+18
	for i in range(n + 1):
		if e < i or h < i:
			break
		max_x = (e - i) // 2
		max_y = (h - i) // 3
		if i + max_x + max_y < n:
			continue
		if s:
			x = min(n - i, max_x)
			y = n - i - x
			price = x * a + y * b + i * c
			ans = min(ans, price)
		else:
			y = min(n - i, max_y)
			x = n - i - y
			price = x * a + y * b + i * c
			ans = min(ans, price)
	if ans == 1e+18:
		ans = -1
	print(ans)


import sys
t = int(input())
for _ in range(t):
	(n, e, h, a, b, c) = list(map(int, input().split()))
	ans = sys.maxsize
	for i in range(min(min(e, h) + 1, n + 1)):
		om = (e - i) // 2
		milk = (h - i) // 3
		cc = i
		if om + milk + cc >= n:
			out = 0
			cnt = cc
			out += cc * c
			if a < b:
				out += min(om, n - cnt) * a
				cnt += min(om, n - cnt)
				out += min(milk, n - cnt) * b
				cnt += min(milk, n - cnt)
			else:
				out += min(milk, n - cnt) * b
				cnt += min(milk, n - cnt)
				out += min(om, n - cnt) * a
				cnt += min(om, n - cnt)
			ans = min(ans, out)
	if ans == sys.maxsize:
		print(-1)
	else:
		print(ans)


for _ in range(int(input())):
	(n, e, h, a, b, c) = map(int, input().split())
	ans = []
	for cakes in range(n + 1):
		if e < cakes or h < cakes:
			break
		if int((e - cakes) / 2) + int((h - cakes) / 3) + cakes < n:
			continue
		else:
			if a < b:
				ro = min(n - cakes, int((e - cakes) / 2))
				rm = n - cakes - ro
			else:
				rm = min(n - cakes, int((h - cakes) / 3))
				ro = n - cakes - rm
			ans.append(rm * b + ro * a + cakes * c)
	if len(ans) == 0:
		print(-1)
	else:
		print(int(min(ans)))


import math
t = int(input())
for _ in range(t):
	(n, e, h, a, b, c) = list(map(int, input().strip().split()))
	min_price = 10 ** 15
	limit = min(e, h, n)
	for z in range(0, limit + 1):
		price = 10 ** 15
		if a >= b:
			y = min(math.floor((h - z) // 3), n - z)
			x = n - y - z
			if x <= math.floor((e - z) // 2):
				price = a * x + b * y + c * z
		elif b > a:
			x = min(math.floor((e - z) // 2), n - z)
			y = n - x - z
			if y <= math.floor((h - z) // 3):
				price = a * x + b * y + c * z
		if price < min_price:
			min_price = price
	if min_price == 10 ** 15:
		print(-1)
	else:
		print(min_price)


def minimum_price(n, e, h, a, b, c):
	flag = 0
	max_price = 0
	for cake in range(n + 1):
		if e < cake or h < cake:
			continue
		maxo = (e - cake) // 2
		maxh = (h - cake) // 3
		if cake + maxo + maxh < n:
			continue
		if a < b:
			reqo = min(n - cake, maxo)
			reqm = n - cake - reqo
		else:
			reqm = min(n - cake, maxh)
			reqo = n - cake - reqm
		price = cake * c + reqo * a + reqm * b
		if max_price == 0:
			max_price = price
		max_price = min(max_price, price)
	if max_price == 0:
		return -1
	else:
		return max_price
t = int(input())
while t > 0:
	(n, e, h, a, b, c) = map(int, input().split())
	print(minimum_price(n, e, h, a, b, c))
	t -= 1


def findPrice(n, nC, a, b, c, e, h):
	price = c * nC
	eRem = e - nC
	hRem = h - nC
	if eRem // 2 + nC + hRem // 3 < n:
		return -1
	if a < b:
		nO = min(n - nC, eRem // 2)
		nM = min(n - nC - nO, hRem // 3)
		price = price + nO * a + nM * b
	else:
		nM = min(n - nC, hRem // 3)
		nO = min(n - nC - nM, eRem // 2)
		price = price + nO * a + nM * b
	return price
t = int(input())
for _ in range(t):
	(n, e, h, a, b, c) = list(map(int, input().strip().split()))
	numCakes = min(e if e < h else h, n)
	eRem = e - numCakes
	hRem = h - numCakes
	if eRem // 2 + numCakes + hRem // 3 < n:
		print(-1)
	else:
		price = findPrice(n, numCakes, a, b, c, e, h)
		for i in range(numCakes - 1, -1, -1):
			curr = findPrice(n, i, a, b, c, e, h)
			if curr == -1:
				continue
			if curr < price:
				price = curr
		print(price)


def findPrice(n, nC, a, b, c, e, h):
	price = c * nC
	eRem = e - nC
	hRem = h - nC
	if eRem // 2 + nC + hRem // 3 < n:
		return -1
	if a < b:
		nO = min(n - nC, eRem // 2)
		nM = min(n - nC - nO, hRem // 3)
		price = price + nO * a + nM * b
	else:
		nM = min(n - nC, hRem // 3)
		nO = min(n - nC - nM, eRem // 2)
		price = price + nO * a + nM * b
	return price
t = int(input())
for _ in range(t):
	(n, e, h, a, b, c) = list(map(int, input().strip().split()))
	numCakes = min(e if e < h else h, n)
	eRem = e - numCakes
	hRem = h - numCakes
	if eRem // 2 + numCakes + hRem // 3 < n:
		print(-1)
	else:
		found = False
		price = -1
		for i in range(numCakes, -1, -1):
			curr = findPrice(n, i, a, b, c, e, h)
			if not found and curr != -1:
				price = curr
				found = True
			elif found and curr != -1 and (curr < price):
				price = curr
		print(price)


for testcase in range(int(input())):
	(items, eggs, chocolates, costometlette, costShake, costCake) = map(int, input().split())
	ans = 10 ** 18
	for cakes in range(items + 1):
		if eggs < cakes or chocolates < cakes:
			break
		omelettes = int((eggs - cakes) / 2)
		shake = int((chocolates - cakes) / 3)
		if cakes + omelettes + shake < items:
			continue
		if costometlette < costShake:
			omelettesReq = min(omelettes, items - cakes)
			shakeReq = items - cakes - omelettesReq
		else:
			shakeReq = min(shake, items - cakes)
			omelettesReq = items - cakes - shakeReq
		finalcost = costCake * cakes + costometlette * omelettesReq + costShake * shakeReq
		ans = min(ans, finalcost)
	if ans == 10 ** 18:
		print(-1)
	else:
		print(ans)


T = int(input())
import sys
while T:
	(N, E, H, A, B, C) = list(map(int, input().split()))
	minprice = sys.maxsize
	for cake in range(N + 1):
		if E < cake or H < cake:
			break
		omlette = (E - cake) // 2
		milkshake = (H - cake) // 3
		if omlette + cake + milkshake < N:
			continue
		if A < B:
			omletteReq = min(omlette, N - cake)
			milkshakeReq = N - cake - omletteReq
		else:
			milkshakeReq = min(milkshake, N - cake)
			omletteReq = N - cake - milkshakeReq
		price = omletteReq * A + milkshakeReq * B + cake * C
		minprice = min(minprice, price)
	if minprice == sys.maxsize:
		print(-1)
	else:
		print(minprice)
	T -= 1


for _ in range(int(input())):
	(N, E, H, A, B, C) = map(int, input().split())
	a = int(1e+18)
	for i in range(N + 1):
		if E < i or H < i:
			break
		nom = (E - i) // 2
		ncm = (H - i) // 3
		if i + nom + ncm < N:
			continue
		if A < B:
			Omr = min(nom, N - i)
			cmr = N - i - Omr
		else:
			cmr = min(ncm, N - i)
			Omr = N - i - cmr
		price = i * C + Omr * A + cmr * B
		a = min(a, price)
	if a == int(1e+18):
		print(-1)
	else:
		print(int(a))


import sys

def get_ints():
	return map(int, sys.stdin.readline().strip().split())

def solve(n, eggs, chocolates, omPrice, shakePrice, cakePrice):
	minPrice = 10 ** 12
	for cake in range(n + 1):
		if eggs < cake or chocolates < cake:
			break
		maxOmellete = (eggs - cake) // 2
		maxChocolates = (chocolates - cake) // 3
		if cake + maxOmellete + maxChocolates < n:
			continue
		if omPrice < shakePrice:
			omelleteReq = min(n - cake, maxOmellete)
			shakesReq = n - cake - omelleteReq
		else:
			shakesReq = min(n - cake, maxChocolates)
			omelleteReq = n - cake - shakesReq
		price = cake * cakePrice + omelleteReq * omPrice + shakesReq * shakePrice
		minPrice = min(price, minPrice)
	if minPrice == 10 ** 12:
		return -1
	return minPrice
t = int(input())
for i in range(t):
	(n, e, h, a, b, c) = get_ints()
	print(solve(n, e, h, a, b, c))


t = int(input())
for _ in range(t):
	(n, e, h, a, b, c) = map(int, input().split())
	mini = set()
	f = 0
	for cake in range(0, n + 1):
		if e < cake or h < cake:
			continue
		maxa = (e - cake) // 2
		maxb = (h - cake) // 3
		if cake + maxa + maxb < n:
			continue
		if a < b:
			ome = min(n - cake, maxa)
			milk = n - cake - ome
		else:
			milk = min(n - cake, maxb)
			ome = n - cake - milk
		price = ome * a + milk * b + cake * c
		mini.add(price)
	if mini == set():
		print(-1)
	else:
		print(min(mini))


try:
	t = int(input())
	for i in range(t):
		(items, eggs, chocolates, price_omlette, price_milkshake, price_cake) = map(int, input().split())
		ans = 1e+18
		for cakes in range(0, items + 1):
			if eggs < cakes or chocolates < cakes:
				break
			omlettes = (eggs - cakes) // 2
			milkshakes = (chocolates - cakes) // 3
			if cakes + milkshakes + omlettes < items:
				continue
			if price_omlette < price_milkshake:
				req_omlettes = min(omlettes, items - cakes)
				req_milkshakes = items - cakes - req_omlettes
			else:
				req_milkshakes = min(milkshakes, items - cakes)
				req_omlettes = items - cakes - req_milkshakes
			price = cakes * price_cake + req_omlettes * price_omlette + req_milkshakes * price_milkshake
			ans = min(ans, price)
		if ans == 1e+18:
			ans = -1
			print(ans)
		else:
			print(ans)
except:
	pass


import math
t = int(input())
for _ in range(t):
	(n, e, h, a, b, c) = [int(x) for x in input().split()]
	ans = math.inf
	for i in range(min(e, h, n), -1, -1):
		cc = i
		if cc < n:
			ans1 = cc * c
			if (e - cc) // 2 + (h - cc) // 3 >= n - cc:
				t1 = min((e - cc) // 2, n - cc)
				t2 = min((h - cc) // 3, n - cc)
				if a <= b:
					ans1 += t1 * a
					ans1 += (n - cc - t1) * b
				else:
					ans1 += t2 * b
					ans1 += (n - cc - t2) * a
			else:
				ans1 = math.inf
			ans = min(ans, ans1)
		else:
			ans = min(ans, n * c)
	if ans == math.inf:
		print(-1)
	else:
		print(ans)


def getMin(n, e, ch, omCost, mkCost, ckCost):
	ans = float('inf')
	(omReq, mkshakeReq) = (0, 0)
	for cakes in range(n + 1):
		if e < cakes or ch < cakes:
			break
		omelettes = (e - cakes) // 2
		milkshakes = (ch - cakes) // 3
		if cakes + omelettes + milkshakes < n:
			continue
		if omCost < mkCost:
			omReq = min(n - cakes, omelettes)
			mkshakeReq = n - cakes - omReq
		else:
			mkshakeReq = min(n - cakes, milkshakes)
			omReq = n - cakes - mkshakeReq
		price = ckCost * cakes + omCost * omReq + mkCost * mkshakeReq
		ans = min(ans, price)
	if ans == float('inf'):
		return -1
	return ans
for i in range(int(input())):
	(n, e, ch, om, mk, ck) = [int(i) for i in input().split()]
	print(getMin(n, e, ch, om, mk, ck))


for TC in range(int(input())):
	(N, E, H, A, B, C) = map(int, input().split())
	result = int(1e+18)
	flag = 0
	for i in range(N + 1):
		if E < i or H < i:
			break
		cost = i * C
		first = N - i
		second = E - i
		third = H - i
		if A < B:
			e1 = min(second // 2, first)
			cost += e1 * A
			first -= e1
			if third // 3 < first:
				continue
			cost += first * B
			result = min(result, cost)
		else:
			b1 = min(third // 3, first)
			cost += b1 * B
			first -= b1
			if second // 2 < first:
				continue
			cost += first * A
			result = min(result, cost)
	if result == int(1e+18):
		print('-1')
	else:
		print(result)


for t in range(int(input())):
	(items, eggs, choclate, omeletteprice, milkshakeprice, cakeprice) = list(map(int, input().split()))
	price = 0
	ans = 1000000000000000
	for cake in range(items + 1):
		if eggs < cake or choclate < cake:
			break
		omelete = (eggs - cake) // 2
		milkshake = (choclate - cake) // 3
		if cake + omelete + milkshake < items:
			continue
		if omeletteprice < milkshakeprice:
			omelete = min(omelete, items - cake)
			milkshake = items - cake - omelete
		else:
			milkshake = min(milkshake, items - cake)
			omelete = items - cake - milkshake
		price = omelete * omeletteprice + milkshake * milkshakeprice + cake * cakeprice
		ans = min(ans, price)
	if ans == 1000000000000000:
		ans = -1
	print(ans)


import math
t = int(input())
while t:
	(N, E, H, A, B, C) = [int(x) for x in input().split()]
	minimum = math.inf
	for z in range(N + 1):
		if E < z or H < z:
			continue
		maxO = (E - z) // 2
		maxM = (H - z) // 3
		if z + maxO + maxM < N:
			continue
		if A < B:
			x = min(N - z, maxO)
			y = N - z - x
		else:
			y = min(N - z, maxM)
			x = N - z - y
		price = z * C + x * A + y * B
		minimum = min(minimum, price)
	if minimum == math.inf:
		print(-1)
	else:
		print(minimum)
	t -= 1


t = int(input())
for _ in range(t):
	(n, e, h, a, b, c) = map(int, input().split())
	(cake, prize, flag) = (n, n * max([a, c, b]), False)
	for ck in range(cake + 1):
		N = ck
		if e < ck or h < ck:
			continue
		elif ck >= n:
			flag = True
			pri = n * c
		elif a <= b:
			pri = ck * c
			om = (e - ck) // 2
			if (h - ck) // 3 >= n - ck - om:
				flag = True
				if om <= n - N:
					pri += om * a
					N += om
					if n - N > 0:
						pri += (n - N) * b
				else:
					pri += (n - N) * a
			else:
				continue
		else:
			pri = ck * c
			cs = (h - ck) // 3
			if (e - ck) // 2 >= n - ck - cs:
				flag = True
				if cs <= n - N:
					pri += cs * b
					N += cs
					if n - N > 0:
						pri += (n - N) * a
				else:
					pri += (n - N) * b
			else:
				continue
		if pri < prize:
			prize = pri
	if flag == True:
		print(prize)
	else:
		print(-1)


t = int(input())
for i in range(t):
	(n, e, h, a, b, c) = map(int, input().split())
	minCost = -1
	for i in range(n + 1):
		cake = i
		if e < cake or h < cake:
			continue
		maxO = (e - cake) // 2
		maxC = (h - cake) // 3
		if maxO + maxC + cake < n:
			continue
		arr = [[a, maxO], [b, maxC], [c, cake]]
		arr.sort()
		cost = 0
		p = n
		for i in range(len(arr)):
			if arr[i][1] > p:
				cost = cost + arr[i][0] * p
				break
			else:
				cost = cost + arr[i][0] * arr[i][1]
				p = p - arr[i][1]
		if minCost == -1:
			minCost = cost
		elif minCost > cost:
			minCost = cost
	print(minCost)


try:
	t = int(input())
	for _ in range(t):
		(n, eggs, bars, price_ome, price_milk, price_cake) = map(int, input().split())
		(w_eggs, w_bars) = (2, 3)
		if price_ome > price_milk:
			(price_ome, price_milk) = (price_milk, price_ome)
			(w_eggs, w_bars) = (w_bars, w_eggs)
			(eggs, bars) = (bars, eggs)
		ans = 10 ** 18
		for cake in range(0, n + 1):
			if eggs >= cake and bars >= cake:
				used_ome = min(n - cake, int((eggs - cake) / w_eggs))
				used_milk = min(n - cake - used_ome, int((bars - cake) / w_bars))
				if cake + used_ome + used_milk == n:
					ans = min(ans, cake * price_cake + used_ome * price_ome + used_milk * price_milk)
		if ans == 10 ** 18:
			ans = -1
		print(ans)
except:
	pass


try:
	for _ in range(int(input())):
		(n, e, h, a, b, c) = list(map(int, input().split()))
		ans = int(1e+18)
		price = 0
		for i in range(n + 1):
			if e < i or h < i:
				break
			oms = int((e - i) / 2)
			mshakes = int((h - i) / 3)
			if i + oms + mshakes < n:
				continue
			if a < b:
				omsreq = int(min(oms, n - i))
				mshakesreq = int(n - i - omsreq)
			else:
				mshakesreq = int(min(mshakes, n - i))
				omsreq = int(n - i - mshakesreq)
			price = int(i * c + omsreq * a + mshakesreq * b)
			ans = min(ans, price)
		if ans == 1e+18:
			ans = -1
		print(ans)
except:
	pass


t = int(input())
while t:
	(n, e, h, a, b, c) = map(int, input().split())
	min_cost = 10 ** 20
	max_z = min(e, h, n)
	for z in range(0, max_z + 1):
		max_x = (e - z) // 2
		max_y = (h - z) // 3
		if max_x + max_y + z < n:
			continue
		if a > b:
			y = min(max_y, n - z)
			x = n - y - z
		else:
			x = min(max_x, n - z)
			y = n - x - z
		min_cost = min(min_cost, a * x + b * y + c * z)
	if min_cost == 10 ** 20:
		print(-1)
	else:
		print(min_cost)
	t = t - 1


t = int(input())
for _ in range(t):
	ans = 10 ** 20
	(n, e, h, a, b, c) = map(int, input().split())
	for cakes in range(n + 1):
		if e < cakes or h < cakes:
			break
		omlet = (e - cakes) // 2
		shake = (h - cakes) // 3
		if cakes + omlet + shake < n:
			continue
		if a < b:
			reqO = min(omlet, n - cakes)
			reqM = n - cakes - reqO
		else:
			reqM = min(shake, n - cakes)
			reqO = n - cakes - reqM
		ans = min(ans, reqO * a + reqM * b + cakes * c)
	if ans == 10 ** 20:
		ans = -1
	print(ans)


t = int(input())
for _ in range(t):
	(n, eggs, choco_bar, cost_om, cost_ms, cost_cake) = list(map(int, input().split()))
	ans = float('inf')
	for cakes in range(n + 1):
		if eggs < cakes or choco_bar < cakes:
			break
		om = (eggs - cakes) // 2
		ms = (choco_bar - cakes) // 3
		if om + cakes + ms < n:
			continue
		if cost_om < cost_ms:
			req_om = min(n - cakes, om)
			req_ms = n - cakes - req_om
		else:
			req_ms = min(n - cakes, ms)
			req_om = n - cakes - req_ms
		price = cakes * cost_cake + req_ms * cost_ms + req_om * cost_om
		ans = min(price, ans)
	if ans == float('inf'):
		print('-1')
	else:
		print(ans)


t = int(input())
for _ in range(t):
	(N, E, H, A, B, C) = list(map(int, input().split(' ')))
	result = float('inf')
	for i in range(N + 1):
		if i > E or i > H:
			break
		c = i
		o = m = 0
		e = E - i
		h = H - i
		Omax = e // 2
		Mmax = h // 3
		if A < B:
			if Omax >= N - i:
				o = N - i
			else:
				o = Omax
				if Mmax >= N - i - o:
					m = N - i - o
				else:
					continue
		elif Mmax >= N - i:
			m = N - i
		else:
			m = Mmax
			if Omax >= N - i - m:
				o = N - i - m
			else:
				continue
		result = min(result, A * o + B * m + C * c)
	if result == float('inf'):
		print(-1)
	else:
		print(result)


for _ in range(int(input())):
	(N, E, H, A, B, C) = map(int, input().split())
	ans = 10 ** 18
	for cakes in range(0, N + 1):
		if E < cakes or H < cakes:
			break
		maxO = (E - cakes) // 2
		maxM = (H - cakes) // 3
		if cakes + maxO + maxM < N:
			continue
		if A < B:
			reqO = min(N - cakes, maxO)
			reqM = N - cakes - reqO
		else:
			reqM = min(N - cakes, maxM)
			reqO = N - cakes - reqM
		price = cakes * C + reqO * A + reqM * B
		ans = min(price, ans)
	if ans == 10 ** 18:
		ans = -1
	print(ans)


import sys
t = int(input())
for _ in range(t):
	(n, e, h, a, b, c) = map(int, input().split())
	ans = sys.maxsize
	price = 0
	for cc in range(n + 1):
		if e < cc or h < cc:
			break
		maxo = (e - cc) // 2
		maxcm = (h - cc) // 3
		if cc + maxo + maxcm < n:
			continue
		if a < b:
			reqo = min(maxo, n - cc)
			reqcm = n - (reqo + cc)
		else:
			reqcm = min(maxcm, n - cc)
			reqo = n - (reqcm + cc)
		price = a * reqo + b * reqcm + c * cc
		ans = min(price, ans)
	if ans == sys.maxsize:
		print(-1)
	else:
		print(ans)


for _ in range(int(input())):
	(items, eggs, chocolates, omeletteCost, milkshakeCost, cakeCost) = map(int, input().split())
	ans = float('inf')
	for cakes in range(items + 1):
		if eggs < cakes or chocolates < cakes:
			break
		maxO = (eggs - cakes) // 2
		maxC = (chocolates - cakes) // 3
		if cakes + maxO + maxC < items:
			continue
		if omeletteCost < milkshakeCost:
			reqO = min(items - cakes, maxO)
			reqC = items - cakes - reqO
		else:
			reqC = min(items - cakes, maxC)
			reqO = items - cakes - reqC
		price = omeletteCost * reqO + milkshakeCost * reqC + cakeCost * cakes
		ans = min(price, ans)
	if ans == float('inf'):
		ans = -1
		print(ans)
	else:
		print(ans)


t = int(input())
for i in range(t):
	(n, e, h, a, b, c) = map(int, input().split())
	cakes = min(e, h)
	eggs_available = max(e - cakes, 0)
	bars_available = max(h - cakes, 0)
	if cakes + int(eggs_available / 2) + int(bars_available / 3) < n:
		print(-1)
		continue
	minimum = 1000000000000000
	j = min(cakes, n)
	while j >= 0:
		eggs_available = e - j
		bars_available = h - j
		temp = j * c
		(temp1, temp2) = (0, 0)
		if a < b:
			temp1 = min(int(eggs_available / 2), n - j)
			temp += temp1 * a
			temp2 = min(int(bars_available / 3), n - j - temp1)
			temp += temp2 * b
		else:
			temp1 = min(int(bars_available / 3), n - j)
			temp += temp1 * b
			temp2 = min(int(eggs_available / 2), n - j - temp1)
			temp += temp2 * a
		if (temp1 < 0) & (temp2 < 0):
			j -= 1
			continue
		if j + temp1 + temp2 < n:
			j -= 1
			continue
		if temp < minimum:
			minimum = temp
		j -= 1
	print(minimum)


for _ in range(int(input())):
	(n, e, h, a, b, c) = map(int, input().split())
	p = 1e+18
	find = False
	for cake in range(0, n + 1, 1):
		if e < cake or h < cake:
			break
		maxo = (e - cake) // 2
		maxm = (h - cake) // 3
		if cake + maxm + maxo < n:
			continue
		if a < b:
			reo = min(n - cake, maxo)
			rem = n - cake - reo
		else:
			rem = min(n - cake, maxm)
			reo = n - cake - rem
		p = min(p, a * reo + b * rem + c * cake)
		find = True
	if find:
		print(p)
	else:
		print(-1)


from math import floor
INF = 1e+18
t = int(input())
for _ in range(t):
	(N, E, H, A, B, C) = list(map(int, input().split()))
	minimum = INF
	for z in range(0, min(N + 1, min(E + 1, H + 1))):
		x = max(0, (E - z) // 2)
		y = max(0, (H - z) // 3)
		if x + y + z < N:
			continue
		if A < B:
			cost = min(x, N - z) * A + z * C + min(y, N - z - min(x, N - z)) * B
		else:
			cost = min(x, N - z - min(y, N - z)) * A + z * C + min(y, N - z) * B
		minimum = min(cost, minimum)
	if minimum == INF:
		print(-1)
	else:
		print(minimum)


try:
	testcase = int(input())
	while testcase > 0:
		(items, eggs, chocolates, omeletteCost, milkshakeCost, cakeCost) = list(map(int, input().split()))
		testcase -= 1
		ans = 1e+18
		for cakes in range(0, items + 1):
			if eggs < cakes or chocolates < cakes:
				break
			omelettes = (eggs - cakes) // 2
			milkshakes = (chocolates - cakes) // 3
			if cakes + omelettes + milkshakes < items:
				continue
			(omelettesreq, milkshakesReq) = (0, 0)
			if omeletteCost < milkshakeCost:
				omelettesReq = min(omelettes, items - cakes)
				milkshakesReq = items - cakes - omelettesReq
			else:
				milkshakesReq = min(milkshakes, items - cakes)
				omelettesReq = items - cakes - milkshakesReq
			price = cakes * cakeCost + omelettesReq * omeletteCost + milkshakesReq * milkshakeCost
			ans = min(ans, price)
		if ans == 1e+18:
			ans = -1
		print(ans)
except:
	pass


for tc in range(int(input())):
	(N, EGG, CHOC, a, b, c) = map(int, input().split())
	sufficient = False
	ans = 1000000000000000000
	for cake in range(0, min(N, min(EGG, CHOC)) + 1):
		(shake, omelete) = (0, 0)
		n = N - cake
		egg = EGG - cake
		choc = CHOC - cake
		if a <= b:
			if egg > 0:
				served = min(n, egg // 2)
				n -= served
				omelete = served
			if n > 0:
				served = min(n, choc // 3)
				n -= served
				shake = served
		else:
			if choc > 0:
				served = min(n, choc // 3)
				n -= served
				shake = served
			if n > 0:
				served = min(n, egg // 2)
				n -= served
				omelete = served
		if n == 0:
			sufficient = True
			ans = min(ans, omelete * a + shake * b + cake * c)
	if sufficient:
		print(ans)
	else:
		print(-1)


def run_one_test_case():
	(N, E, H, A, B, C) = list(map(int, input().split()))
	min_cost = None
	for xc in range(min(E, H, N) + 1):
		max_omelette = (E - xc) // 2
		max_milkshake = (H - xc) // 3
		if xc + max_omelette + max_milkshake < N:
			continue
		if A < B:
			xa = min(N - xc, max_omelette)
			xb = N - xc - xa
		else:
			xb = min(N - xc, max_milkshake)
			xa = N - xc - xb
		cost = xa * A + xb * B + xc * C
		if min_cost is None or cost < min_cost:
			min_cost = cost
	print(min_cost) if min_cost else print(-1)

def run_one_test_case_old():
	(N, E, H, A, B, C) = list(map(int, input().split()))
	min_cost = None
	for xa in range(min(E // 2 + 1, N + 1)):
		for xb in range(min(H // 3 + 1, N - xa + 1)):
			xc = N - xa - xb
			if 2 * xa + xc <= E and 3 * xb + xc <= H:
				cost = xa * A + xb * B + xc * C
				if min_cost is None or cost < min_cost:
					min_cost = cost
	print(min_cost) if min_cost else print(-1)

def main():
	for _ in range(int(input())):
		run_one_test_case()
main()


try:
	for i in range(int(input())):
		(n, e, h, a, b, c) = map(int, input().split())
		ans = int(1e+18)
		for j in range(n + 1):
			if e < j or h < j:
				break
			cost = j * c
			egg = e - j
			l = n - j
			bar = h - j
			if a < b:
				om = min(l, egg // 2)
				cost += om * a
				l -= om
				if bar // 3 < l:
					continue
				cost += l * b
				ans = min(cost, ans)
			else:
				milk = min(l, bar // 3)
				cost += milk * b
				l -= milk
				if egg // 2 < l:
					continue
				cost += l * a
				ans = min(ans, cost)
		if ans == int(1e+18):
			print('-1')
		else:
			print(ans)
except:
	pass