{"problem":{"name":"C. Ahmad and Spells","description":{"content":"Ahmad has recently started playing a new game called DotA (Defense of the Agents), which is a very interesting computer game, and currently he is learning a new strategy for winning with his special h","description_type":"Markdown"},"platform":"Codeforces","limit":{"time_limit":1000,"memory_limit":262144},"difficulty":"None","is_remote":true,"is_sync":true,"sync_url":null,"sign":"CF10150C"},"statements":[{"statement_type":"Markdown","content":"Ahmad has recently started playing a new game called DotA (Defense of the Agents), which is a very interesting computer game, and currently he is learning a new strategy for winning with his special hero \"Chimpanzee King\". In order to perform the strategy, the hero must execute n spells.\n\nInitially, each spell needs x seconds of channeling to be executed, but Ahmad knows two ways that can reduce the channeling time, which are: \n\nThe total number of mana-points that Ahmad spends should not exceed s.\n\nAhmad wants to use this strategy at its best, so he is interested in the minimum time he needs to spend in order to execute n spells.\n\nThe first line of the input contains an integer T, where T is the number of test cases.\n\nThe first line of each test case contains three integers n, m, and k (1 ≤ n ≤ 2 × 109, 1 ≤ m, k ≤ 105), where n is the number of spells Ahmad has to execute, m is the number of talents, and k is the number of heroes.\n\nThe second line of each test case contains two integers x and s (2 ≤ x ≤ 2 × 109, 1 ≤ s ≤ 2 × 109), where x is the initial number of seconds required to channel one spell, and s is the number of mana-points Ahmad can use.\n\nThe third line of each test case contains m integers a1, a2, ..., am (1 ≤ ai ≤ x), where ai is the number of seconds it will take to prepare one potion of the ith spell from the first type.\n\nThe fourth line of each test case contains m integers b1, b2, ..., bm (1 ≤ bi ≤ 2 × 109), where bi is the number of required mana-points to use the ith spell from the first type.\n\nThe fifth line of each test case contains k integers c1, c2, ..., ck (1 ≤ ci ≤ n), where ci is the number of potions that will be immediately created if the ith spell from the second type was used.\n\nThe sixth line of each test case contains k integers d1, d2, ..., dk (1 ≤ di ≤ 2 × 109), where di is the number of mana-points required to use the ith spell from the second type.\n\nFor each test case, print a single line containing the minimum time Ahmad has to spend in order to prepare n potions.\n\nAs input/output can reach huge size it is recommended to use fast input/output methods: for example, prefer to use _scanf/printf_ instead of _cin/cout_ in C++, prefer to use _BufferedReader/PrintWriter_ instead of _Scanner/System.out_ in Java.\n\n## Input\n\nThe first line of the input contains an integer T, where T is the number of test cases.The first line of each test case contains three integers n, m, and k (1 ≤ n ≤ 2 × 109, 1 ≤ m, k ≤ 105), where n is the number of spells Ahmad has to execute, m is the number of talents, and k is the number of heroes.The second line of each test case contains two integers x and s (2 ≤ x ≤ 2 × 109, 1 ≤ s ≤ 2 × 109), where x is the initial number of seconds required to channel one spell, and s is the number of mana-points Ahmad can use.The third line of each test case contains m integers a1, a2, ..., am (1 ≤ ai ≤ x), where ai is the number of seconds it will take to prepare one potion of the ith spell from the first type.The fourth line of each test case contains m integers b1, b2, ..., bm (1 ≤ bi ≤ 2 × 109), where bi is the number of required mana-points to use the ith spell from the first type.The fifth line of each test case contains k integers c1, c2, ..., ck (1 ≤ ci ≤ n), where ci is the number of potions that will be immediately created if the ith spell from the second type was used.The sixth line of each test case contains k integers d1, d2, ..., dk (1 ≤ di ≤ 2 × 109), where di is the number of mana-points required to use the ith spell from the second type.\n\n## Output\n\nFor each test case, print a single line containing the minimum time Ahmad has to spend in order to prepare n potions.\n\n[samples]\n\n## Note\n\nAs input/output can reach huge size it is recommended to use fast input/output methods: for example, prefer to use _scanf/printf_ instead of _cin/cout_ in C++, prefer to use _BufferedReader/PrintWriter_ instead of _Scanner/System.out_ in Java.","is_translate":false,"language":"English"},{"statement_type":"Markdown","content":"**Definitions**  \nLet $ T \\in \\mathbb{Z} $ be the number of test cases.  \nFor each test case:  \n- Let $ n \\in \\mathbb{Z} $ be the number of spells to execute.  \n- Let $ m, k \\in \\mathbb{Z} $ be the number of talents (type-1 abilities) and heroes (type-2 abilities), respectively.  \n- Let $ x \\in \\mathbb{Z} $ be the initial channeling time per spell.  \n- Let $ s \\in \\mathbb{Z} $ be the maximum available mana-points.  \n- Let $ A = (a_1, \\dots, a_m) \\in \\mathbb{Z}^m $, where $ a_i $ is the channeling time for one potion using talent $ i $.  \n- Let $ B = (b_1, \\dots, b_m) \\in \\mathbb{Z}^m $, where $ b_i $ is the mana cost for talent $ i $.  \n- Let $ C = (c_1, \\dots, c_k) \\in \\mathbb{Z}^k $, where $ c_j $ is the number of potions instantly created by hero $ j $.  \n- Let $ D = (d_1, \\dots, d_k) \\in \\mathbb{Z}^k $, where $ d_j $ is the mana cost for hero $ j $.  \n\n**Constraints**  \n1. $ 1 \\le T \\le \\text{large} $ (input-dependent)  \n2. $ 1 \\le n \\le 2 \\times 10^9 $  \n3. $ 1 \\le m, k \\le 10^5 $  \n4. $ 2 \\le x \\le 2 \\times 10^9 $  \n5. $ 1 \\le s \\le 2 \\times 10^9 $  \n6. $ 1 \\le a_i \\le x $ for all $ i \\in \\{1, \\dots, m\\} $  \n7. $ 1 \\le b_i \\le 2 \\times 10^9 $ for all $ i \\in \\{1, \\dots, m\\} $  \n8. $ 1 \\le c_j \\le n $ for all $ j \\in \\{1, \\dots, k\\} $  \n9. $ 1 \\le d_j \\le 2 \\times 10^9 $ for all $ j \\in \\{1, \\dots, k\\} $  \n\n**Objective**  \nMinimize the total channeling time to produce exactly $ n $ potions, subject to total mana cost $ \\le s $, using:  \n- Type-1 abilities: Use talent $ i $ to reduce channeling time per potion to $ a_i $, at cost $ b_i $ mana (can be used multiple times).  \n- Type-2 abilities: Use hero $ j $ to instantly create $ c_j $ potions, at cost $ d_j $ mana (can be used at most once per hero).  \n\nLet $ t \\in \\mathbb{R}_{\\ge 0} $ be the total time.  \nLet $ p \\in \\mathbb{Z}_{\\ge 0} $ be the number of potions produced via type-2 abilities.  \nLet $ r = n - p \\ge 0 $ be the remaining potions produced via type-1 abilities.  \n\nFor fixed $ p $, the minimal time is:  \n$$\nt(p) = \\min_{\\substack{J \\subseteq \\{1,\\dots,k\\} \\\\ \\sum_{j \\in J} c_j = p \\\\ \\sum_{j \\in J} d_j \\le s}} \\left( \\min_{\\substack{i \\in \\{1,\\dots,m\\} \\\\ \\sum_{j \\in J} d_j + b_i \\le s}} \\left( r \\cdot a_i \\right) \\right)\n$$  \nBut since type-1 abilities can be used repeatedly and independently, define:  \n- $ a_{\\min} = \\min_{i=1}^m a_i $  \n- $ b_{\\min} = \\min_{i=1}^m b_i $  \n\nThen, for a subset $ J \\subseteq \\{1,\\dots,k\\} $ producing $ p = \\sum_{j \\in J} c_j $ potions:  \n- Mana left: $ s' = s - \\sum_{j \\in J} d_j $  \n- If $ s' \\ge 0 $, then $ r = n - p $ potions can be produced at time $ r \\cdot a_{\\min} $, provided $ s' \\ge b_{\\min} $ (to enable type-1 use); if $ s' < b_{\\min} $, then type-1 cannot be used → only feasible if $ r = 0 $.  \n\nThus, the objective is:  \n$$\n\\min_{\\substack{J \\subseteq \\{1,\\dots,k\\} \\\\ \\sum_{j \\in J} c_j \\le n \\\\ \\sum_{j \\in J} d_j \\le s}} \\left( \\begin{cases} \n(n - \\sum_{j \\in J} c_j) \\cdot a_{\\min} & \\text{if } \\sum_{j \\in J} d_j + b_{\\min} \\le s \\text{ or } n = \\sum_{j \\in J} c_j \\\\\n\\infty & \\text{otherwise}\n\\end{cases} \\right)\n$$\n\n**Note**: Since $ k \\le 10^5 $, but $ 2^k $ is infeasible, we must optimize by considering only Pareto-optimal hero combinations (by mana cost vs. potions produced), and use greedy/dynamic programming on sorted hero list. However, the formal objective remains as above.","is_translate":false,"language":"Formal"}],"meta":{"iden":"CF10150C","tags":[],"sample_group":[],"created_at":"2026-03-03 11:00:39"}}