Virtual contest is a way to take part in past contest, as close as possible to participation on time. It is supported only ICPC mode for virtual contests.
If you've seen these problems, a virtual contest is not for you - solve these problems in the archive.
If you just want to solve some problem from a contest, a virtual contest is not for you - solve this problem in the archive.
Never use someone else's code, read the tutorials or communicate with other person during a virtual contest.

brute force

dp

meet-in-the-middle

*2100

No tag edit access

The problem statement has recently been changed. View the changes.

×
D. Field expansion

time limit per test

1 secondmemory limit per test

256 megabytesinput

standard inputoutput

standard outputIn 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.

Codeforces (c) Copyright 2010-2024 Mike Mirzayanov

The only programming contests Web 2.0 platform

Server time: Apr/25/2024 04:05:28 (j3).

Desktop version, switch to mobile version.

Supported by

User lists

Name |
---|