In one of the games Arkady is fond of the game process happens on a rectangular field. In the game process Arkady can buy extensions for his field, each extension enlarges one of the field sizes in a particular number of times. Formally, there are n extensions, the i-th of them multiplies the width or the length (by Arkady's choice) by a_{i}. Each extension can't be used more than once, the extensions can be used in any order.

Now Arkady's field has size h × w. He wants to enlarge it so that it is possible to place a rectangle of size a × b on it (along the width or along the length, with sides parallel to the field sides). Find the minimum number of extensions needed to reach Arkady's goal.


-----Input-----

The first line contains five integers a, b, h, w and n (1 ≤ a, b, h, w, n ≤ 100 000) — the sizes of the rectangle needed to be placed, the initial sizes of the field and the number of available extensions.

The second line contains n integers a_1, a_2, ..., a_{n} (2 ≤ a_{i} ≤ 100 000), where a_{i} equals the integer a side multiplies by when the i-th extension is applied.


-----Output-----

Print the minimum number of extensions needed to reach Arkady's goal. If it is not possible to place the rectangle on the field with all extensions, print -1. If the rectangle can be placed on the initial field, print 0.


-----Examples-----
Input
3 3 2 4 4
2 5 4 10

Output
1

Input
3 3 3 3 5
2 3 5 4 2

Output
0

Input
5 5 1 2 3
2 2 3

Output
-1

Input
3 4 1 1 3
2 3 2

Output
3



-----Note-----

In the first example it is enough to use any of the extensions available. For example, we can enlarge h in 5 times using the second extension. Then h becomes equal 10 and it is now possible to place the rectangle on the field.

Difficulty: HARD
Tags: Dynamic programming

Complete search
Skill types: Dynamic programming

Complete search

Starter code:

Solutions:
def isin(a, b, h, w):
	return h >= a and w >= b or (h >= b and w >= a)
(a, b, h, w, n) = map(int, input().split())
c = sorted(list(map(int, input().split())), key=lambda x: -x)
if isin(a, b, h, w):
	print(0)
	exit()
vis = {h: w}
for i in range(len(c)):
	nc = c[i]
	pairs = []
	for l in vis.keys():
		pair = (l, vis[l] * nc)
		if isin(a, b, pair[0], pair[1]):
			print(i + 1)
			exit()
		pairs.append(pair)
		if nc * l not in vis or vis[l] > vis[nc * l]:
			pair = (nc * l, vis[l])
			if isin(a, b, pair[0], pair[1]):
				print(i + 1)
				exit()
			pairs.append(pair)
	for p in pairs:
		vis[p[0]] = p[1]
print(-1)


(a, b, h, w, n) = list(map(int, input().strip().split(' ')))
if a > b:
	(a, b) = (b, a)
factor = list(map(int, input().strip().split(' ')))
factor = sorted(factor)[::-1]

def findout(a, b, h, w, factor):
	possible = set()
	for i in range(len(factor)):
		temp = set()
		if i == 0:
			temp.add((factor[0], 1))
			temp.add((1, factor[0]))
			possible = temp
			for X in temp:
				(f1, f2) = X
				if f1 * h >= a and f2 * w >= b:
					return i + 1
		else:
			for X in possible:
				(c1, c2) = X
				if c1 * h <= a:
					temp.add((c1 * factor[i], c2))
					if c1 * factor[i] * h >= a and c2 * w >= b:
						return i + 1
				if c2 * w <= b:
					temp.add((c1, c2 * factor[i]))
					if c1 * h >= a and c2 * w * factor[i] >= b:
						return i + 1
			possible = temp
	return 10 ** 9 + 1
if h >= a and w >= b or (h >= b and w >= a):
	print(0)
else:
	ans = min(findout(a, b, h, w, factor), findout(a, b, w, h, factor))
	if ans != 10 ** 9 + 1:
		print(ans)
	else:
		print(-1)


def gen(o, gen1):
	if o == len(my_arr):
		fp = 1
		sp = 1
		for i in range(len(my_arr)):
			fp *= my_arr[i][0] ** gen1[i]
			sp *= my_arr[i][0] ** (my_arr[i][1] - gen1[i])
		if h * fp >= a and w * sp >= b or (h * fp >= b and w * sp >= a):
			return True
		return False
	for i in range(my_arr[o][1] + 1):
		if gen(o + 1, gen1 + [i]):
			return True
	return False
(a, b, h, w, n) = map(int, input().split())
arr = list(map(int, input().split()))
arr.sort(reverse=True)
arr2 = []
for i in range(n):
	if not i or arr[i] != arr[i - 1]:
		arr2.append([arr[i], 1])
	else:
		arr2[-1][1] += 1
if h >= a and w >= b or (h >= b and w >= a):
	print(0)
else:
	my_arr = []
	j = -1
	ans = -1
	for i in range(1, min(34, len(arr)) + 1):
		if my_arr and my_arr[-1] < arr2[j]:
			my_arr[-1][1] += 1
		else:
			j += 1
			my_arr.append([arr2[j][0], 1])
		if gen(0, []):
			ans = i
			break
	print(ans)


import sys
MAXV = 100010
d = [0] * MAXV
(a, b, h, w, n) = list(map(int, input().split()))
arr = input().split()
for it in range(n):
	arr[it] = int(arr[it])

def solve(a, b, h, w, z, product, it):
	k = 0
	if a % h:
		k = a // h + 1
	else:
		k = a // h
	if k <= z and product // z * w >= b:
		print(it)
		return
arr = sorted(arr)
arr = arr[::-1]
d[1] = 1
solve(a, b, h, w, 1, 1, 0)
solve(a, b, w, h, 1, 1, 0)
product = 1
xxx = 0
for it in range(1, n + 1):
	product *= arr[it - 1]
	for j in reversed(list(range(1, MAXV))):
		if not d[j]:
			continue
		x = j * arr[it - 1]
		if x < MAXV:
			d[x] = 1
		elif xxx:
			xxx = min(x, xxx)
		else:
			xxx = x
	if xxx:
		solve(a, b, h, w, xxx, product, it)
		solve(a, b, w, h, xxx, product, it)
	for j in range(MAXV):
		if d[j]:
			solve(a, b, h, w, j, product, it)
			solve(a, b, w, h, j, product, it)
print(-1)


f = lambda : list(map(int, input().split()))
(a, b, h, w, n) = f()
c = sorted(list(f()), key=lambda x: -x)
d = {(h, w), (w, h)}
for (i, q) in enumerate([1] + c):
	for (u, v) in d.copy():
		(h, w) = (u, v * q)
		if a <= w and b <= h or (a <= h and b <= w):
			print(i)
			return
		d.add((h, w))
		d.add((w, h))
print(-1)


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

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

def pt(x):
	print(x)

def ip():
	return input()

def it():
	return int(input())

def sl(x):
	return [t for t in x]

def spl(x):
	return x.split()

def aj(liste, item):
	liste.append(item)

def bin(x):
	return '{0:b}'.format(x)

def listring(l):
	return ' '.join([str(x) for x in l])

def ptlist(l):
	print(' '.join([str(x) for x in l]))
from copy import deepcopy
(c, b, h, w, n) = mp()
d = lt()
d.sort(reverse=True)
k = min(n, 34)
a = d[:k]
if c <= h and b <= w or (c <= w and b <= h):
	pt(0)
else:
	dict = {h: w}
	i = 0
	bl = True
	while bl and i < k:
		x = a[i]
		dict1 = {}
		for r in dict:
			if r * x in dict1:
				dict1[r * x] = max(dict1[r * x], dict[r])
			else:
				dict1[r * x] = dict[r]
			if r in dict1:
				dict1[r] = max(dict1[r], dict[r] * x)
			else:
				dict1[r] = dict[r] * x
		if any((r >= c and dict1[r] >= b or (r >= b and dict1[r] >= c) for r in dict1)):
			bl = False
		else:
			i += 1
			dict = deepcopy(dict1)
	if i == k:
		pt(-1)
	else:
		pt(i + 1)