{"raw_statement":[{"iden":"statement","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 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.\n\nNow 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."},{"iden":"input","content":"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.\n\nThe 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."},{"iden":"output","content":"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_."},{"iden":"examples","content":"Input\n\n3 3 2 4 4\n2 5 4 10\n\nOutput\n\n1\n\nInput\n\n3 3 3 3 5\n2 3 5 4 2\n\nOutput\n\n0\n\nInput\n\n5 5 1 2 3\n2 2 3\n\nOutput\n\n\\-1\n\nInput\n\n3 4 1 1 3\n2 3 2\n\nOutput\n\n3"},{"iden":"note","content":"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."}],"translated_statement":[{"iden":"statement","content":"在阿卡迪喜欢的一款游戏中，游戏过程发生在矩形场地上。在游戏中，阿卡迪可以购买扩展项来扩大他的场地，每个扩展项会将场地的宽度或长度（由阿卡迪选择）乘以一个特定的数值。形式上，共有 #cf_span[n] 个扩展项，第 #cf_span[i] 个扩展项可以将宽度或长度乘以 #cf_span[ai]。每个扩展项最多只能使用一次，且扩展项的使用顺序可以任意。\n\n目前阿卡迪的场地大小为 #cf_span[h × w]。他希望扩大场地，使得可以将一个大小为 #cf_span[a × b] 的矩形放置在场地上（沿宽度或长度方向放置，且边与场地边平行）。求达到阿卡迪目标所需的最少扩展项数量。\n\n第一行包含五个整数 #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]) —— 分别表示需要放置的矩形尺寸、场地的初始尺寸以及可用扩展项的数量。\n\n第二行包含 #cf_span[n] 个整数 #cf_span[a1, a2, ..., an] (#cf_span[2 ≤ ai ≤ 100 000])，其中 #cf_span[ai] 表示第 #cf_span[i] 个扩展项应用时，某一边所乘的整数。\n\n请输出达到阿卡迪目标所需的最少扩展项数量。如果使用所有扩展项后仍无法放置该矩形，请输出 _-1_。如果矩形已经可以放置在初始场地上，请输出 _0_。\n\n在第一个例子中，只需使用任意一个可用的扩展项即可。例如，我们可以使用第二个扩展项将 #cf_span[h] 扩大 #cf_span[5] 倍，此时 #cf_span[h] 变为 #cf_span[10]，矩形即可被放置在场地上。"},{"iden":"input","content":"第一行包含五个整数 #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] 个扩展项应用时，某一边所乘的整数。"},{"iden":"output","content":"请输出达到阿卡迪目标所需的最少扩展项数量。如果使用所有扩展项后仍无法放置该矩形，请输出 _-1_。如果矩形已经可以放置在初始场地上，请输出 _0_。"},{"iden":"examples","content":"输入3 3 2 4 42 5 4 10输出1输入3 3 3 3 52 3 5 4 2输出0输入5 5 1 2 32 2 3输出-1输入3 4 1 1 32 3 2输出3"},{"iden":"note","content":"在第一个例子中，只需使用任意一个可用的扩展项即可。例如，我们可以使用第二个扩展项将 #cf_span[h] 扩大 #cf_span[5] 倍，此时 #cf_span[h] 变为 #cf_span[10]，矩形即可被放置在场地上。"}],"sample_group":[],"show_order":[],"formal_statement":"**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 of multipliers, where $ a_i \\geq 2 $.  \n\n**Constraints**  \n1. $ 1 \\leq a, b, h, w, n \\leq 100{,}000 $  \n2. $ 2 \\leq a_i \\leq 100{,}000 $ for all $ i \\in \\{1, \\dots, n\\} $  \n\n**Objective**  \nFind 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:  \n$$\n(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\n$$  \nor  \n$$\n(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\n$$  \nwhere $ S_h \\cup S_w $ is a subset of $ \\{1, \\dots, n\\} $ of size $ k $, and $ S_h \\cap S_w = \\emptyset $.  \n\nIf no such $ k $ exists, return $ -1 $. If $ h \\geq a $ and $ w \\geq b $, or $ h \\geq b $ and $ w \\geq a $, return $ 0 $.","simple_statement":null,"has_page_source":false}