{"problem":{"name":"C. Anton and Making Potions","description":{"content":"Anton is playing a very interesting computer game, but now he is stuck at one of the levels. To pass to the next level he has to prepare _n_ potions. Anton has a special kettle, that can prepare one ","description_type":"Markdown"},"platform":"Codeforces","limit":{"time_limit":4000,"memory_limit":262144},"difficulty":"None","is_remote":true,"is_sync":true,"sync_url":null,"sign":"CF734C"},"statements":[{"statement_type":"Markdown","content":"Anton is playing a very interesting computer game, but now he is stuck at one of the levels. To pass to the next level he has to prepare _n_ potions.\n\nAnton has a special kettle, that can prepare one potions in _x_ seconds. Also, he knows spells of two types that can faster the process of preparing potions.\n\n1.  Spells of this type speed up the preparation time of one potion. There are _m_ spells of this type, the _i_\\-th of them costs _b__i_ manapoints and changes the preparation time of each potion to _a__i_ instead of _x_.\n2.  Spells of this type immediately prepare some number of potions. There are _k_ such spells, the _i_\\-th of them costs _d__i_ manapoints and instantly create _c__i_ potions.\n\nAnton can use **no more than one** spell of the first type and **no more than one** spell of the second type, and the total number of manapoints spent should not exceed _s_. Consider that all spells are used instantly and right before Anton starts to prepare potions.\n\nAnton wants to get to the next level as fast as possible, so he is interested in the minimum number of time he needs to spent in order to prepare at least _n_ potions.\n\n## Input\n\nThe first line of the input contains three integers _n_, _m_, _k_ (1 ≤ _n_ ≤ 2·109, 1 ≤ _m_, _k_ ≤ 2·105) — the number of potions, Anton has to make, the number of spells of the first type and the number of spells of the second type.\n\nThe second line of the input contains two integers _x_ and _s_ (2 ≤ _x_ ≤ 2·109, 1 ≤ _s_ ≤ 2·109) — the initial number of seconds required to prepare one potion and the number of manapoints Anton can use.\n\nThe third line contains _m_ integers _a__i_ (1 ≤ _a__i_ < _x_) — the number of seconds it will take to prepare one potion if the _i_\\-th spell of the first type is used.\n\nThe fourth line contains _m_ integers _b__i_ (1 ≤ _b__i_ ≤ 2·109) — the number of manapoints to use the _i_\\-th spell of the first type.\n\nThere are _k_ integers _c__i_ (1 ≤ _c__i_ ≤ _n_) in the fifth line — the number of potions that will be immediately created if the _i_\\-th spell of the second type is used. It's guaranteed that _c__i_ are **not decreasing**, i.e. _c__i_ ≤ _c__j_ if _i_ < _j_.\n\nThe sixth line contains _k_ integers _d__i_ (1 ≤ _d__i_ ≤ 2·109) — the number of manapoints required to use the _i_\\-th spell of the second type. It's guaranteed that _d__i_ are **not decreasing**, i.e. _d__i_ ≤ _d__j_ if _i_ < _j_.\n\n## Output\n\nPrint one integer — the minimum time one has to spent in order to prepare _n_ potions.\n\n[samples]\n\n## Note\n\nIn the first sample, the optimum answer is to use the second spell of the first type that costs 10 manapoints. Thus, the preparation time of each potion changes to 4 seconds. Also, Anton should use the second spell of the second type to instantly prepare 15 potions spending 80 manapoints. The total number of manapoints used is 10 + 80 = 90, and the preparation time is 4·5 = 20 seconds (15 potions were prepared instantly, and the remaining 5 will take 4 seconds each).\n\nIn the second sample, Anton can't use any of the spells, so he just prepares 20 potions, spending 10 seconds on each of them and the answer is 20·10 = 200.","is_translate":false,"language":"English"},{"statement_type":"Markdown","content":"Anton 正在玩一个非常有趣的电脑游戏，但现在他卡在了其中一个关卡。为了进入下一关，他需要准备 #cf_span[n] 种药水。\n\nAnton 有一个特殊的水壶，可以在 #cf_span[x] 秒内制作一种药水。此外，他掌握了两种类型的法术，可以加快药水的制作过程。\n\nAnton 最多可以使用一个第一类法术和一个第二类法术，且消耗的法力值总和不能超过 #cf_span[s]。假设所有法术都是立即生效，并在 Anton 开始制作药水之前使用。\n\nAnton 希望尽可能快地进入下一关，因此他希望找到制作至少 #cf_span[n] 种药水所需的最少时间。\n\n输入的第一行包含三个整数 #cf_span[n], #cf_span[m], #cf_span[k] (#cf_span[1 ≤ n ≤ 2·109, 1 ≤ m, k ≤ 2·105]) —— Anton 需要制作的药水数量、第一类法术的数量和第二类法术的数量。\n\n第二行包含两个整数 #cf_span[x] 和 #cf_span[s] (#cf_span[2 ≤ x ≤ 2·109, 1 ≤ s ≤ 2·109]) —— 初始制作一种药水所需的秒数以及 Anton 可用的法力值。\n\n第三行包含 #cf_span[m] 个整数 #cf_span[ai] (#cf_span[1 ≤ ai < x]) —— 如果使用第 #cf_span[i] 种第一类法术，制作一种药水所需的时间（秒）。\n\n第四行包含 #cf_span[m] 个整数 #cf_span[bi] (#cf_span[1 ≤ bi ≤ 2·109]) —— 使用第 #cf_span[i] 种第一类法术所需的法力值。\n\n第五行包含 #cf_span[k] 个整数 #cf_span[ci] (#cf_span[1 ≤ ci ≤ n]) —— 如果使用第 #cf_span[i] 种第二类法术，将立即生成的药水数量。保证 #cf_span[ci] 是**非递减**的，即当 #cf_span[i < j] 时，#cf_span[ci ≤ cj]。\n\n第六行包含 #cf_span[k] 个整数 #cf_span[di] (#cf_span[1 ≤ di ≤ 2·109]) —— 使用第 #cf_span[i] 种第二类法术所需的法力值。保证 #cf_span[di] 是**非递减**的，即当 #cf_span[i < j] 时，#cf_span[di ≤ dj]。\n\n请输出一个整数 —— 制作 #cf_span[n] 种药水所需的最少时间。\n\n在第一个样例中，最优方案是使用第二种第一类法术，消耗 #cf_span[10] 点法力值，使每种药水的制作时间变为 #cf_span[4] 秒。同时，Anton 应使用第二种第二类法术，立即生成 #cf_span[15] 种药水，消耗 #cf_span[80] 点法力值。总法力值消耗为 #cf_span[10 + 80 = 90]，制作时间为 #cf_span[4·5 = 20] 秒（#cf_span[15] 种药水立即生成，剩余的 #cf_span[5] 种每种耗时 #cf_span[4] 秒）。\n\n在第二个样例中，Anton 无法使用任何法术，因此他只能直接制作 #cf_span[20] 种药水，每种耗时 #cf_span[10] 秒，答案为 #cf_span[20·10 = 200]。\n\n## Input\n\n输入的第一行包含三个整数 #cf_span[n], #cf_span[m], #cf_span[k] (#cf_span[1 ≤ n ≤ 2·109, 1 ≤ m, k ≤ 2·105]) —— Anton 需要制作的药水数量、第一类法术的数量和第二类法术的数量。第二行包含两个整数 #cf_span[x] 和 #cf_span[s] (#cf_span[2 ≤ x ≤ 2·109, 1 ≤ s ≤ 2·109]) —— 初始制作一种药水所需的秒数以及 Anton 可用的法力值。第三行包含 #cf_span[m] 个整数 #cf_span[ai] (#cf_span[1 ≤ ai < x]) —— 如果使用第 #cf_span[i] 种第一类法术，制作一种药水所需的时间（秒）。第四行包含 #cf_span[m] 个整数 #cf_span[bi] (#cf_span[1 ≤ bi ≤ 2·109]) —— 使用第 #cf_span[i] 种第一类法术所需的法力值。第五行包含 #cf_span[k] 个整数 #cf_span[ci] (#cf_span[1 ≤ ci ≤ n]) —— 如果使用第 #cf_span[i] 种第二类法术，将立即生成的药水数量。保证 #cf_span[ci] 是**非递减**的，即当 #cf_span[i < j] 时，#cf_span[ci ≤ cj]。第六行包含 #cf_span[k] 个整数 #cf_span[di] (#cf_span[1 ≤ di ≤ 2·109]) —— 使用第 #cf_span[i] 种第二类法术所需的法力值。保证 #cf_span[di] 是**非递减**的，即当 #cf_span[i < j] 时，#cf_span[di ≤ dj]。\n\n## Output\n\n请输出一个整数 —— 制作 #cf_span[n] 种药水所需的最少时间。\n\n[samples]\n\n## Note\n\n在第一个样例中，最优方案是使用第二种第一类法术，消耗 #cf_span[10] 点法力值，使每种药水的制作时间变为 #cf_span[4] 秒。同时，Anton 应使用第二种第二类法术，立即生成 #cf_span[15] 种药水，消耗 #cf_span[80] 点法力值。总法力值消耗为 #cf_span[10 + 80 = 90]，制作时间为 #cf_span[4·5 = 20] 秒（#cf_span[15] 种药水立即生成，剩余的 #cf_span[5] 种每种耗时 #cf_span[4] 秒）。在第二个样例中，Anton 无法使用任何法术，因此他只能直接制作 #cf_span[20] 种药水，每种耗时 #cf_span[10] 秒，答案为 #cf_span[20·10 = 200]。","is_translate":true,"language":"Chinese"},{"statement_type":"Markdown","content":"**Definitions**  \nLet $ n \\in \\mathbb{Z}^+ $ be the number of potions needed.  \nLet $ m, k \\in \\mathbb{Z}^+ $ be the number of spells of type 1 and type 2, respectively.  \nLet $ x \\in \\mathbb{Z}^+ $ be the base time (seconds) to prepare one potion.  \nLet $ s \\in \\mathbb{Z}^+ $ be the maximum manapoints available.  \n\nLet $ A = (a_1, \\dots, a_m) $ be the reduced time per potion for type-1 spells, where $ 1 \\le a_i < x $.  \nLet $ B = (b_1, \\dots, b_m) $ be the manapoint cost for type-1 spells.  \nLet $ C = (c_1, \\dots, c_k) $ be the number of instantly created potions for type-2 spells, non-decreasing.  \nLet $ D = (d_1, \\dots, d_k) $ be the manapoint cost for type-2 spells, non-decreasing.  \n\n**Constraints**  \n1. $ 1 \\le n \\le 2 \\cdot 10^9 $  \n2. $ 1 \\le m, k \\le 2 \\cdot 10^5 $  \n3. $ 2 \\le x \\le 2 \\cdot 10^9 $, $ 1 \\le s \\le 2 \\cdot 10^9 $  \n4. $ 1 \\le a_i < x $, $ 1 \\le b_i \\le 2 \\cdot 10^9 $  \n5. $ 1 \\le c_i \\le n $, $ c_i \\le c_j $ for $ i < j $  \n6. $ 1 \\le d_i \\le 2 \\cdot 10^9 $, $ d_i \\le d_j $ for $ i < j $  \n7. Use **at most one** type-1 spell and **at most one** type-2 spell, with total manapoint cost $ \\le s $.  \n\n**Objective**  \nMinimize the total time $ T $ to prepare at least $ n $ potions:  \n$$\nT = \\min_{\\substack{i \\in \\{0, \\dots, m\\} \\\\ j \\in \\{0, \\dots, k\\} \\\\ b_i + d_j \\le s}} \\left( \\max\\left(0, n - c_j\\right) \\cdot a_i \\right)\n$$  \nwhere:  \n- $ a_0 = x $, $ b_0 = 0 $ (no type-1 spell used),  \n- $ c_0 = 0 $, $ d_0 = 0 $ (no type-2 spell used).","is_translate":false,"language":"Formal"}],"meta":{"iden":"CF734C","tags":["binary search","dp","greedy","two pointers"],"sample_group":[["20 3 2\n10 99\n2 4 3\n20 10 40\n4 15\n10 80","20"],["20 3 2\n10 99\n2 4 3\n200 100 400\n4 15\n100 800","200"]],"created_at":"2026-03-03 11:00:39"}}