{"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 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.\n\n## Input\n\nThe 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.\n\n## Output\n\nPrint 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_.\n\n[samples]\n\n## Note\n\nIn 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.","is_translate":false,"language":"English"},{"statement_type":"Markdown","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]，矩形即可被放置在场地上。\n\n## Input\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]) —— 分别表示需要放置的矩形尺寸、场地的初始尺寸以及可用扩展项的数量。第二行包含 #cf_span[n] 个整数 #cf_span[a1, a2, ..., an] (#cf_span[2 ≤ ai ≤ 100 000])，其中 #cf_span[ai] 表示第 #cf_span[i] 个扩展项应用时，某一边所乘的整数。\n\n## Output\n\n请输出达到阿卡迪目标所需的最少扩展项数量。如果使用所有扩展项后仍无法放置该矩形，请输出 _-1_。如果矩形已经可以放置在初始场地上，请输出 _0_。\n\n[samples]\n\n## Note\n\n在第一个例子中，只需使用任意一个可用的扩展项即可。例如，我们可以使用第二个扩展项将 #cf_span[h] 扩大 #cf_span[5] 倍，此时 #cf_span[h] 变为 #cf_span[10]，矩形即可被放置在场地上。","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 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 $.","is_translate":false,"language":"Formal"}],"meta":{"iden":"CF799D","tags":["brute force","dp","meet-in-the-middle"],"sample_group":[["3 3 2 4 4\n2 5 4 10","1"],["3 3 3 3 5\n2 3 5 4 2","0"],["5 5 1 2 3\n2 2 3","\\-1"],["3 4 1 1 3\n2 3 2","3"]],"created_at":"2026-03-03 11:00:39"}}