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: competition

Starter code:

Solutions:
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])

# print(arr)
# print(a, b, h, w, n)

def solve(a, b, h, w, z, product, it):
    # print(">", 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]
# print(arr)

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):
    # arr[it - 1] = int(arr[it - 1])
    product *= arr[it - 1]
    # print("=", arr[it - 1])

    for j in reversed(list(range(1, MAXV))):
        if not d[j]:
            continue

        x = j * arr[it - 1]
        # x = min(x, MAXV - 1)
        if x < MAXV:
            d[x] = 1
        else:
            if 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)


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)

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)
    return

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)
            return
        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)
                return
            pairs.append(pair)
    for p in pairs:
        vis[p[0]] = p[1]
print(-1)

def mp():  return list(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)
        
    
            
        
    


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]
#print(factor)
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)
                
                
            
            
            
            
            
            
    
    
    
    
    
    
    
    
    


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 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)