Field expansion

题意翻译

给出一个$a*b$的目标矩形和一个$h*w$的现有矩形以及$n$个操作。每个操作有一个数$a_i$，该可将现有矩形h边乘上$a_i$，或将w边乘上$a_i$。问至少进行几次操作，可以使得目标矩形能放入现有矩形中（可以旋转90度）。若无解，请输出-1

题目描述

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.

输入输出格式

输入格式

The first line contains five integers $ a $ , $ b $ , $ h $ , $ w $ and $ n $ ( $ 1<=a,b,h,w,n<=100000 $ ) — 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}<=100000 $ ), where $ a_{i} $ equals the integer a side multiplies by when the $ i $ -th extension is applied.

输出格式

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.

输入输出样例

输入样例 #1

3 3 2 4 4
2 5 4 10

输出样例 #1

1

输入样例 #2

3 3 3 3 5
2 3 5 4 2

输出样例 #2

0

输入样例 #3

5 5 1 2 3
2 2 3

输出样例 #3

-1

输入样例 #4

3 4 1 1 3
2 3 2

输出样例 #4

3

说明

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.