{"problem":{"name":"M. It's complicated","description":{"content":"Dragon was drinking tea on a balcony and admiring a very beautiful sunset. Two outgoing silhouettes were still descrying in the rays of a setting sun. Of course, Princess promised to visit Dragon some","description_type":"Markdown"},"platform":"Codeforces","limit":{"time_limit":2000,"memory_limit":262144},"difficulty":"None","is_remote":true,"is_sync":true,"sync_url":null,"sign":"CF10070M"},"statements":[{"statement_type":"Markdown","content":"Dragon was drinking tea on a balcony and admiring a very beautiful sunset. Two outgoing silhouettes were still descrying in the rays of a setting sun. Of course, Princess promised to visit Dragon sometime, but what could be a reason for her to come back in the Castles Valley?..\n\nDragon decided to cook biscuits according to a recipe that was told him by Princess. So he needs to check if he has sufficient quantity of ingredients for it. Of course, he has a few of ginger, cinnamon, cloves and cardamon... But, comparing to making tea, he needs some more ingredients to bake biscuits.\n\nDragon revised all his ingredients, and knew how many units of each ingredient he had.\n\nIt was written in the recipe how many units of each ingredient are required to bake a biscuit. Certainly, Dragon wanted to bake an integer number of biscuits.\n\nDragon realized that he will expend some ingredients completely, while some other ingredients will remain. He believed he must purchase some extra ingredients, so that all ingredients will be completely expended after baking some number of biscuits.\n\nDragon knew the cost for a unit of each ingredient. Your task is to figure out minimum amount of money which is needed to spend to fulfil the condition above.\n\nThe first line contains integer n (1 ≤ n ≤ 10) — the number of ingredients.\n\nThe second line contains n integers q1, q2, ..., qn (1 ≤ qj ≤ 100,  j = 1, 2, ..., n), qj — the number of units of jth ingredient, which Dragon has.\n\nThe third line contains n integers c1, c2, ..., cn (1 ≤ cj ≤ 10,  j = 1, 2, ..., n), cj — the number of units of jth ingredient which it needs for cooking a biscuit.\n\nThe fourth line contains n integers p1, p2, ..., pn (1 ≤ pj ≤ 100,  j = 1, 2, ..., n), pj — cost of a unit of jth ingredient.\n\nPrint the only integer — minimum amount of money to spend.\n\n## Input\n\nThe first line contains integer n (1 ≤ n ≤ 10) — the number of ingredients.The second line contains n integers q1, q2, ..., qn (1 ≤ qj ≤ 100,  j = 1, 2, ..., n), qj — the number of units of jth ingredient, which Dragon has.The third line contains n integers c1, c2, ..., cn (1 ≤ cj ≤ 10,  j = 1, 2, ..., n), cj — the number of units of jth ingredient which it needs for cooking a biscuit.The fourth line contains n integers p1, p2, ..., pn (1 ≤ pj ≤ 100,  j = 1, 2, ..., n), pj — cost of a unit of jth ingredient.\n\n## Output\n\nPrint the only integer — minimum amount of money to spend.\n\n[samples]","is_translate":false,"language":"English"},{"statement_type":"Markdown","content":"**Definitions**  \nLet $ n \\in \\mathbb{Z}^+ $ be the number of ingredients.  \nLet $ \\mathbf{q} = (q_1, \\dots, q_n) \\in \\mathbb{Z}^n $ be the available units of each ingredient.  \nLet $ \\mathbf{c} = (c_1, \\dots, c_n) \\in \\mathbb{Z}^n $ be the units required per biscuit for each ingredient.  \nLet $ \\mathbf{p} = (p_1, \\dots, p_n) \\in \\mathbb{Z}^n $ be the cost per unit of each ingredient.  \n\nLet $ k \\in \\mathbb{Z}^+ $ be the number of biscuits to bake.  \n\n**Constraints**  \n1. $ 1 \\leq n \\leq 10 $  \n2. $ 1 \\leq q_j \\leq 100 $ for all $ j \\in \\{1, \\dots, n\\} $  \n3. $ 1 \\leq c_j \\leq 10 $ for all $ j \\in \\{1, \\dots, n\\} $  \n4. $ 1 \\leq p_j \\leq 100 $ for all $ j \\in \\{1, \\dots, n\\} $  \n\n**Objective**  \nFind the minimum cost:  \n$$\n\\min_{k \\in \\mathbb{Z}^+} \\sum_{j=1}^{n} p_j \\cdot \\left( (k \\cdot c_j) \\bmod q_j \\right)\n$$  \nwhere the deficit for ingredient $ j $ is $ (k \\cdot c_j - q_j) \\bmod c_j $ if $ k \\cdot c_j > q_j $, else $ c_j - (q_j \\bmod c_j) $ if $ q_j \\bmod c_j \\neq 0 $, and 0 otherwise.  \n\nEquivalently, for each $ j $, define the additional units needed for $ k $ biscuits as:  \n$$\nd_j(k) = \\begin{cases}\n0 & \\text{if } q_j \\equiv 0 \\pmod{c_j} \\text{ and } k \\equiv 0 \\pmod{q_j / c_j} \\\\\n(k \\cdot c_j - q_j) \\bmod c_j & \\text{if } k \\cdot c_j \\geq q_j \\\\\nc_j - (q_j \\bmod c_j) & \\text{if } k \\cdot c_j < q_j \\text{ and } q_j \\bmod c_j \\neq 0\n\\end{cases}\n$$  \nBut since $ k $ must be chosen so that **all** $ q_j + \\text{purchased}_j $ are divisible by $ c_j $, we require:  \n$$\nk \\cdot c_j \\geq q_j \\quad \\text{and} \\quad k \\cdot c_j \\equiv 0 \\pmod{\\gcd(c_j, q_j)} \\quad \\text{(redundant)}\n$$  \nActually, simpler:  \nWe need $ k \\cdot c_j \\geq q_j $ and $ k \\cdot c_j \\equiv 0 \\pmod{c_j} $ (always true), so we require:  \n$$\nk \\geq \\left\\lceil \\frac{q_j}{c_j} \\right\\rceil \\quad \\text{for all } j\n$$  \nThen the amount to buy for ingredient $ j $ is:  \n$$\nb_j(k) = k \\cdot c_j - q_j\n$$  \nTotal cost:  \n$$\nC(k) = \\sum_{j=1}^{n} p_j \\cdot (k \\cdot c_j - q_j)\n$$  \nSubject to:  \n$$\nk \\geq \\max_{1 \\leq j \\leq n} \\left\\lceil \\frac{q_j}{c_j} \\right\\rceil\n$$  \n\n**Objective (Final)**  \n$$\n\\min_{k \\in \\mathbb{Z},\\, k \\geq \\max_j \\left\\lceil \\frac{q_j}{c_j} \\right\\rceil} \\sum_{j=1}^{n} p_j (k c_j - q_j)\n$$","is_translate":false,"language":"Formal"}],"meta":{"iden":"CF10070M","tags":[],"sample_group":[],"created_at":"2026-03-03 11:00:39"}}