little-fajlu-and-aoe-2

Little Fajlu and Laal Baadshah are extremely good, and passionate Age of Empires 2 players. They're crazy about the game, and the passion they display for the game, if displayed for their semester exams - will make them top the university, even. But well, that's them.

Laal Baadshah relies on rushing through the game, so he tries to create as many weird units as quick as possible, without realizing how much power and strength his total army is giving him. While, Little Fajlu is an extremely smart player - he plans his games in a very smart, and strategic manner... which makes it very difficult to defeat him. Really. Not kidding.

We want the problem solvers to learn Fajlu's strategy, too. So, here it goes.
The top three units he uses are: Samurai, Paladins, and Champions.
The cost of a Samurai is: 100 food, 0 gold.
The cost of a Paladin is: 125 food, 50 gold.
The cost of a Champion is: 50 food, 100 gold.

What Fajlu does is given the state of his current economy, and how much will each unit increase his total advantage over his opponent, he manages to get the maximum army strength he can manage to get.

What you need to do is to calculate this amount quickly, faster than Fajlu and let Laal Baadshah know how much strength will he need to overcome Fajlu?

Input format:
The first line contains a number, T, denoting the number of test cases. The next line contains SIX integers. 
 1. The amount of food F Fajlu has, where  1 ≤ F ≤ 40000
 2. The amount of gold G Fajlu has, where 1 ≤ G ≤ 40000
 3. Power of a Samurai S, where 1 ≤ S ≤ 1000
 4. Power of a Paladin P , where 1 ≤ P ≤ 1000
 5. Power of a Champion C, where 1 ≤ C ≤ 1000
 6. Total power Power Laal Baadshah already has, where 1 ≤ Power ≤ 3000

1 ≤ T ≤ 100  

Output format:
You've to print how much more power would Laal Baadshah need to defeat Fajlu. If he already has more or equal power to defeat him, print -1.

PS: The image contains violent deaths. Adult supervision required. 

SAMPLE INPUT
1
389 130 16 13 18 24

SAMPLE OUTPUT
42

Source: hackerearth | Difficulty: EASY
Tags: Fundamentals

Ad-hoc


Solutions:
for _ in range(eval(input())):
	F, G, S, P, C, Power = list(map(int, input().split()))
	mxS = F/100
	ans = 0
	for i in range(mxS + 1):
		f = F - (i * 100)
		g = G
		p = i * S
		mxP = min(f/125, g/50)
		for j in range(mxP + 1):
			p2 = p
			f2 = f - (j * 125)
			g2 = g - (j * 50)
			mxC = min(f2/50, g2/100)
			p2 += j*P
			p2 += mxC*C
			ans = max(p2, ans)
	ans = ans - Power
	if ans <= 0:
		ans = -1
	print(ans)