English · Original
Chinese · Translation
Formal · Original
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_.
[samples]
## 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.
在阿卡迪喜欢的一款游戏中，游戏过程发生在矩形场地上。在游戏中，阿卡迪可以购买扩展项来扩大他的场地，每个扩展项会将场地的宽度或长度（由阿卡迪选择）乘以一个特定的数值。形式上，共有 #cf_span[n] 个扩展项，第 #cf_span[i] 个扩展项可以将宽度或长度乘以 #cf_span[ai]。每个扩展项最多只能使用一次，且扩展项的使用顺序可以任意。
目前阿卡迪的场地大小为 #cf_span[h × w]。他希望扩大场地，使得可以将一个大小为 #cf_span[a × b] 的矩形放置在场地上（沿宽度或长度方向放置，且边与场地边平行）。求达到阿卡迪目标所需的最少扩展项数量。
第一行包含五个整数 #cf_span[a], #cf_span[b], #cf_span[h], #cf_span[w] 和 #cf_span[n] (#cf_span[1 ≤ a, b, h, w, n ≤ 100 000]) —— 分别表示需要放置的矩形尺寸、场地的初始尺寸以及可用扩展项的数量。
第二行包含 #cf_span[n] 个整数 #cf_span[a1, a2, ..., an] (#cf_span[2 ≤ ai ≤ 100 000])，其中 #cf_span[ai] 表示第 #cf_span[i] 个扩展项应用时，某一边所乘的整数。
请输出达到阿卡迪目标所需的最少扩展项数量。如果使用所有扩展项后仍无法放置该矩形，请输出 _-1_。如果矩形已经可以放置在初始场地上，请输出 _0_。
在第一个例子中，只需使用任意一个可用的扩展项即可。例如，我们可以使用第二个扩展项将 #cf_span[h] 扩大 #cf_span[5] 倍，此时 #cf_span[h] 变为 #cf_span[10]，矩形即可被放置在场地上。
## Input
第一行包含五个整数 #cf_span[a], #cf_span[b], #cf_span[h], #cf_span[w] 和 #cf_span[n] (#cf_span[1 ≤ a, b, h, w, n ≤ 100 000]) —— 分别表示需要放置的矩形尺寸、场地的初始尺寸以及可用扩展项的数量。第二行包含 #cf_span[n] 个整数 #cf_span[a1, a2, ..., an] (#cf_span[2 ≤ ai ≤ 100 000])，其中 #cf_span[ai] 表示第 #cf_span[i] 个扩展项应用时，某一边所乘的整数。
## Output
请输出达到阿卡迪目标所需的最少扩展项数量。如果使用所有扩展项后仍无法放置该矩形，请输出 _-1_。如果矩形已经可以放置在初始场地上，请输出 _0_。
[samples]
## Note
在第一个例子中，只需使用任意一个可用的扩展项即可。例如，我们可以使用第二个扩展项将 #cf_span[h] 扩大 #cf_span[5] 倍，此时 #cf_span[h] 变为 #cf_span[10]，矩形即可被放置在场地上。
**Definitions**
Let $ a, b, h, w, n \in \mathbb{Z}^+ $ denote the target rectangle dimensions, initial field dimensions, and number of extensions.
Let $ A = (a_1, a_2, \dots, a_n) $ be a sequence of multipliers, where $ a_i \geq 2 $.
**Constraints**
1. $ 1 \leq a, b, h, w, n \leq 100{,}000 $
2. $ 2 \leq a_i \leq 100{,}000 $ for all $ i \in \{1, \dots, n\} $
**Objective**
Find the minimum $ k \in \{0, 1, \dots, n\} $ such that there exists a subset of $ k $ extensions (each used at most once) and an assignment of each selected extension to either the height or the width, so that:
$$
(h \cdot \prod_{i \in S_h} a_i) \geq a \quad \text{and} \quad (w \cdot \prod_{j \in S_w} a_j) \geq b
$$
or
$$
(h \cdot \prod_{i \in S_h} a_i) \geq b \quad \text{and} \quad (w \cdot \prod_{j \in S_w} a_j) \geq a
$$
where $ S_h \cup S_w $ is a subset of $ \{1, \dots, n\} $ of size $ k $, and $ S_h \cap S_w = \emptyset $.
If no such $ k $ exists, return $ -1 $. If $ h \geq a $ and $ w \geq b $, or $ h \geq b $ and $ w \geq a $, return $ 0 $.
API Response (JSON)
{
"problem": {
"name": "D. Field expansion",
"description": {
"content": "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 ",
"description_type": "Markdown"
},
"platform": "Codeforces",
"limit": {
"time_limit": 1000,
"memory_limit": 262144
},
"difficulty": "None",
"is_remote": true,
"is_sync": true,
"sync_url": null,
"sign": "CF799D"
},
"statements": [
{
"statement_type": "Markdown",
"content": "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 ...",
"is_translate": false,
"language": "English"
},
{
"statement_type": "Markdown",
"content": "在阿卡迪喜欢的一款游戏中，游戏过程发生在矩形场地上。在游戏中，阿卡迪可以购买扩展项来扩大他的场地，每个扩展项会将场地的宽度或长度（由阿卡迪选择）乘以一个特定的数值。形式上，共有 #cf_span[n] 个扩展项，第 #cf_span[i] 个扩展项可以将宽度或长度乘以 #cf_span[ai]。每个扩展项最多只能使用一次，且扩展项的使用顺序可以任意。\n\n目前阿卡迪的场地大小为 #cf_span[h...",
"is_translate": true,
"language": "Chinese"
},
{
"statement_type": "Markdown",
"content": "**Definitions** \nLet $ a, b, h, w, n \\in \\mathbb{Z}^+ $ denote the target rectangle dimensions, initial field dimensions, and number of extensions. \nLet $ A = (a_1, a_2, \\dots, a_n) $ be a sequence ...",
"is_translate": false,
"language": "Formal"
}
]
}