Problem Statement
Olivia, another cyborg with crafted legs is a very dear friend of Geneo. On the eve of valentines day, Olivia decides to surprise Geneo by arriving at his home with a gift. The gift is special, so is her way of reaching home.

Olivia's legs are driven by batteries and can deliver only a fixed amount of energy. Once she has charged the batteries for certain period, she knows exactly how much energy they contain. Let this energy be P. She wants to completely consume the energy in travelling so that she gets to stay at Geneo's home longer under the guise of charging the batteries.

As it is 2042, the roads in town form a perfect rectangular maze. Olivia lives at the corner (0,0) and Geneo lives at position (X_{Geneo}, Y_{Geneo}). Each direction (North, South, East and West) has its associated per unit travel costs given by C_{North}, C_{South}, C_{East} and C_{West}. Her aim is that the energy left after reaching Geneo's home should be exactly zero.

Note 1: You can assume the town to be laid out infinitely in all the directions.

Note 2: The following are the meaning of directions:
North : From (x, y) to (x, y + 1)
South : From (x, y) to (x, y - 1)
East : From (x, y) to (x + 1, y)
West : From (x, y) to (x - 1, y)

------ Input section ------ 

The first line of the input contains an integer T denoting the number of test cases. The description of T test cases follows.

The first line of each test case contains 7 space separated integers, X_{Geneo}, Y_{Geneo}, C_{North}, C_{South}, C_{East}, C_{West} and P as described in the statement above.

------ Output section ------ 

For each test case, output a single line containing the minimum amount of distance taken by Olivia to reach Geneo with zero energy remaining

If the energy cannot be made zero without violating the constraints, print -1

------ Input constraints ------ 

1 ≤ T ≤ 200

1 ≤ X_{Geneo}, Y_{Geneo} ≤ 10^{3}

1 ≤ C_{North}, C_{South}, C_{East}, C_{West} ≤ 10^{3}

1 ≤ P ≤ 10^{6}

----- Sample Input 1 ------ 
4
10 8 9 1 9 1 90
2 3 4 4 2 2 20
346 36 580 403 656 10 906997
73 544 559 336 831 759 707865
----- Sample Output 1 ------ 
-1
7
2092
-1
----- explanation 1 ------ 
For the second test case, one of the possible paths is : (0, 0) -> (1, 0) -> (2, 0) -> (2, 1) -> (2, 2) -> (2, 3) -> (3, 3) -> (2, 3).
This walk is of length 7, and the directions taken at each step are E, E, N, N, N, E, W. So the total energy spent is 2 + 2 + 4 + 4 + 4 + 2 + 2 = 20, which means that she reached the house with 0 energy left.

Difficulty: HARD
Tags: Number theory

Starter code:

Solutions:
t = int(input())
for i in range(t):
	(x, y, n, s, e, w, p) = map(int, input().split())
	wa = x * e + y * n
	c = x + y
	p -= wa
	if p < 0:
		print(-1)
	elif p == 0:
		print(x + y)
	else:
		li = [n + s, e + w]
		li.sort(reverse=True)
		j = 0
		while p % li[0] != 0:
			p -= li[1]
			j += 2
			if p == 0:
				print(x + y + j)
			if p < 0:
				print(-1)
				break
		if p > 0:
			j += 2 * p // li[0]
			print(x + y + j)


for _ in range(int(input())):
	(X, Y, N, S, E, W, P) = map(int, input().split())
	if X * E + Y * N > P:
		print(-1)
	else:
		P -= X * E + Y * N
		D = X + Y
		Max = max(N + S, E + W)
		Min = min(N + S, E + W)
		ct1 = P // Max
		ct2 = 0
		temp = ct1 * Max
		while ct1 >= 0:
			while temp < P:
				temp += Min
				ct2 += 1
			if temp == P:
				D += 2 * (ct1 + ct2)
				break
			temp -= Max
			ct1 -= 1
		if ct1 < 0:
			print(-1)
		else:
			print(D)


for i in range(int(input())):
	(x, y, n, s, e, w, p) = map(int, input().split())
	p -= x * e + y * n
	if p < 0:
		print(-1)
	else:
		(a, b) = (n + s, e + w)
		i = 0
		temp = 0
		ans = 10 ** 9
		while p >= b * i:
			if (p - b * i) % a == 0:
				ans = min(ans, i + (p - b * i) // a)
			i += 1
		print(-1 if ans == 10 ** 9 else ans * 2 + x + y)


for nitish in range(int(input())):
	(x, y, n, s, e, w, p) = map(int, input().strip().split(' '))
	ss = x + y
	p = p - x * e - y * n
	waste = max(n + s, e + w)
	wastee = min(n + s, e + w)
	lol = p % waste
	lolol = p // waste
	loll = lol // wastee
	if p < 0:
		print(-1)
		continue
	if p == 0:
		print(ss)
		continue
	while lol % wastee != 0 and lolol >= 0:
		lolol -= 1
		lol = p - waste * lolol
		loll = lol // wastee
	if lolol >= 0 and loll >= 0 and (lolol * waste + loll * wastee == p):
		print(lolol * 2 + loll * 2 + ss)
		continue
	else:
		print(-1)
		continue


for i in range(int(input())):
	(x, y, n, s, e, w, p) = map(int, input().split())
	c = y * n + x * e
	if c > p:
		print('-1')
	elif c == p:
		print(int(x + y))
	else:
		lel = sorted([n + s, e + w], reverse=True)
		rem = p - c
		count = 0
		while rem % lel[0] != 0:
			rem -= lel[1]
			count += 2
			if rem == 0:
				print(int(x + y + count))
			if rem < 0:
				print('-1')
				break
		if rem > 0:
			count += 2 * int(rem / lel[0])
			print(int(x + y + count))


def main():
	from sys import stdin, stdout
	rl = stdin.readline
	wl = stdout.write
	int1 = int
	str1 = str
	r1 = range
	t = int1(rl())
	for i in r1(t):
		(x, y, n, s, e, w, p) = [int1(x) for x in rl().split()]
		c = n * y + e * x
		if c > p:
			wl('-1\n')
		elif c == p:
			wl(str1(x + y) + '\n')
		else:
			cs = sorted([n + s, e + w], reverse=True)
			ca = p - c
			j = 0
			while ca % cs[0] != 0:
				ca -= cs[1]
				j += 2
				if ca == 0:
					wl(str1(x + y + j) + '\n')
				if ca < 0:
					wl('-1\n')
					break
			if ca > 0:
				j += 2 * int1(ca / cs[0])
				wl(str1(x + y + j) + '\n')
main()


t = int(input())
for i in range(0, t):
	(x, y, x1, x2, x3, x4, p) = map(int, input().split(' '))
	c = 0
	j = 0
	ans = 1000000000
	i = 0
	while p - x1 * y - x3 * x - (x1 + x2) * i >= 0 and i <= 1000000:
		if (p - x1 * y - x3 * x - (x1 + x2) * i) % (x3 + x4) == 0:
			j = (p - x1 * y - x3 * x - (x1 + x2) * i) // (x3 + x4)
			c += 1
			ans = min(ans, x + y + 2 * (i + j))
		i += 1
	if c == 0:
		print(-1)
	else:
		print(ans)


for _ in range(int(input().strip())):
	(xg, yg, cn, cs, ce, cw, p) = tuple(map(int, input().strip().split()))
	least = cn * yg + ce * xg
	ud = cn + cs
	lr = ce + cw
	req = p - least
	ss = None if req else 0
	for x in range(0, req // ud + 1):
		if (req - ud * x) % lr == 0:
			t = 2 * (x + (req - ud * x) // lr)
			if ss is not None:
				ss = min(t, ss)
			else:
				ss = t
	print(ss + xg + yg if ss is not None else '-1')


def ii():
	return int(input())

def mi():
	return map(int, input().split())

def li():
	return list(mi())
INF = 10 ** 9
for t in range(ii()):
	(X, Y, Cy1, Cy2, Cx1, Cx2, P) = mi()
	P -= Cx1 * X + Cy1 * Y
	if P < 0:
		print(-1)
		continue
	(a, b) = (Cy1 + Cy2, Cx1 + Cx2)
	ans = INF
	i = 0
	while a * i <= P:
		q = P - a * i
		if q % b == 0:
			ans = min(ans, i + q // b)
		i += 1
	print(-1 if ans == INF else ans * 2 + X + Y)