{"trustable":true,"prependHtml":"\u003cstyle type\u003d\u0027text/css\u0027\u003e\n .input, .output {\n border: 1px solid #888888;\n }\n .output {\n margin-bottom: 1em;\n position: relative;\n top: -1px;\n }\n .output pre, .input pre {\n background-color: #EFEFEF;\n line-height: 1.25em;\n margin: 0;\n padding: 0.25em;\n }\n \u003c/style\u003e\n \u003clink rel\u003d\"stylesheet\" href\u003d\"//codeforces.org/s/96598/css/problem-statement.css\" type\u003d\"text/css\" /\u003e\u003cscript\u003e window.katexOptions \u003d { disable: true }; \u003c/script\u003e\n\u003cscript type\u003d\"text/x-mathjax-config\"\u003e\n MathJax.Hub.Config({\n tex2jax: {\n inlineMath: [[\u0027$$$\u0027,\u0027$$$\u0027], [\u0027$\u0027,\u0027$\u0027]],\n displayMath: [[\u0027$$$$$$\u0027,\u0027$$$$$$\u0027], [\u0027$$\u0027,\u0027$$\u0027]]\n }\n });\n\u003c/script\u003e\n\u003cscript type\u003d\"text/javascript\" async src\u003d\"https://mathjax.codeforces.org/MathJax.js?config\u003dTeX-AMS_HTML-full\"\u003e\u003c/script\u003e","sections":[{"title":"","value":{"format":"HTML","content":"\u003cp\u003eAnton 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 \u003cspan class\u003d\"tex-span\"\u003e\u003ci\u003en\u003c/i\u003e\u003c/span\u003e potions.\u003c/p\u003e\u003cp\u003eAnton has a special kettle, that can prepare one potions in \u003cspan class\u003d\"tex-span\"\u003e\u003ci\u003ex\u003c/i\u003e\u003c/span\u003e seconds. Also, he knows spells of two types that can faster the process of preparing potions.\u003c/p\u003e\u003col\u003e \u003cli\u003e Spells of this type speed up the preparation time of one potion. There are \u003cspan class\u003d\"tex-span\"\u003e\u003ci\u003em\u003c/i\u003e\u003c/span\u003e spells of this type, the \u003cspan class\u003d\"tex-span\"\u003e\u003ci\u003ei\u003c/i\u003e\u003c/span\u003e-th of them costs \u003cspan class\u003d\"tex-span\"\u003e\u003ci\u003eb\u003c/i\u003e\u003csub class\u003d\"lower-index\"\u003e\u003ci\u003ei\u003c/i\u003e\u003c/sub\u003e\u003c/span\u003e manapoints and changes the preparation time of each potion to \u003cspan class\u003d\"tex-span\"\u003e\u003ci\u003ea\u003c/i\u003e\u003csub class\u003d\"lower-index\"\u003e\u003ci\u003ei\u003c/i\u003e\u003c/sub\u003e\u003c/span\u003e instead of \u003cspan class\u003d\"tex-span\"\u003e\u003ci\u003ex\u003c/i\u003e\u003c/span\u003e. \u003c/li\u003e\u003cli\u003e Spells of this type immediately prepare some number of potions. There are \u003cspan class\u003d\"tex-span\"\u003e\u003ci\u003ek\u003c/i\u003e\u003c/span\u003e such spells, the \u003cspan class\u003d\"tex-span\"\u003e\u003ci\u003ei\u003c/i\u003e\u003c/span\u003e-th of them costs \u003cspan class\u003d\"tex-span\"\u003e\u003ci\u003ed\u003c/i\u003e\u003csub class\u003d\"lower-index\"\u003e\u003ci\u003ei\u003c/i\u003e\u003c/sub\u003e\u003c/span\u003e manapoints and instantly create \u003cspan class\u003d\"tex-span\"\u003e\u003ci\u003ec\u003c/i\u003e\u003csub class\u003d\"lower-index\"\u003e\u003ci\u003ei\u003c/i\u003e\u003c/sub\u003e\u003c/span\u003e potions. \u003c/li\u003e\u003c/ol\u003e\u003cp\u003eAnton can use \u003cspan class\u003d\"tex-font-style-bf\"\u003eno more than one\u003c/span\u003e spell of the first type and \u003cspan class\u003d\"tex-font-style-bf\"\u003eno more than one\u003c/span\u003e spell of the second type, and the total number of manapoints spent should not exceed \u003cspan class\u003d\"tex-span\"\u003e\u003ci\u003es\u003c/i\u003e\u003c/span\u003e. Consider that all spells are used instantly and right before Anton starts to prepare potions.\u003c/p\u003e\u003cp\u003eAnton 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 \u003cspan class\u003d\"tex-span\"\u003e\u003ci\u003en\u003c/i\u003e\u003c/span\u003e potions.\u003c/p\u003e"}},{"title":"Input","value":{"format":"HTML","content":"\u003cp\u003eThe first line of the input contains three integers \u003cspan class\u003d\"tex-span\"\u003e\u003ci\u003en\u003c/i\u003e\u003c/span\u003e, \u003cspan class\u003d\"tex-span\"\u003e\u003ci\u003em\u003c/i\u003e\u003c/span\u003e, \u003cspan class\u003d\"tex-span\"\u003e\u003ci\u003ek\u003c/i\u003e\u003c/span\u003e (\u003cspan class\u003d\"tex-span\"\u003e1 ≤ \u003ci\u003en\u003c/i\u003e ≤ 2·10\u003csup class\u003d\"upper-index\"\u003e9\u003c/sup\u003e, 1 ≤ \u003ci\u003em\u003c/i\u003e, \u003ci\u003ek\u003c/i\u003e ≤ 2·10\u003csup class\u003d\"upper-index\"\u003e5\u003c/sup\u003e\u003c/span\u003e)\u0026nbsp;— 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.\u003c/p\u003e\u003cp\u003eThe second line of the input contains two integers \u003cspan class\u003d\"tex-span\"\u003e\u003ci\u003ex\u003c/i\u003e\u003c/span\u003e and \u003cspan class\u003d\"tex-span\"\u003e\u003ci\u003es\u003c/i\u003e\u003c/span\u003e (\u003cspan class\u003d\"tex-span\"\u003e2 ≤ \u003ci\u003ex\u003c/i\u003e ≤ 2·10\u003csup class\u003d\"upper-index\"\u003e9\u003c/sup\u003e, 1 ≤ \u003ci\u003es\u003c/i\u003e ≤ 2·10\u003csup class\u003d\"upper-index\"\u003e9\u003c/sup\u003e\u003c/span\u003e)\u0026nbsp;— the initial number of seconds required to prepare one potion and the number of manapoints Anton can use.\u003c/p\u003e\u003cp\u003eThe third line contains \u003cspan class\u003d\"tex-span\"\u003e\u003ci\u003em\u003c/i\u003e\u003c/span\u003e integers \u003cspan class\u003d\"tex-span\"\u003e\u003ci\u003ea\u003c/i\u003e\u003csub class\u003d\"lower-index\"\u003e\u003ci\u003ei\u003c/i\u003e\u003c/sub\u003e\u003c/span\u003e (\u003cspan class\u003d\"tex-span\"\u003e1 ≤ \u003ci\u003ea\u003c/i\u003e\u003csub class\u003d\"lower-index\"\u003e\u003ci\u003ei\u003c/i\u003e\u003c/sub\u003e \u0026lt; \u003ci\u003ex\u003c/i\u003e\u003c/span\u003e)\u0026nbsp;— the number of seconds it will take to prepare one potion if the \u003cspan class\u003d\"tex-span\"\u003e\u003ci\u003ei\u003c/i\u003e\u003c/span\u003e-th spell of the first type is used.\u003c/p\u003e\u003cp\u003eThe fourth line contains \u003cspan class\u003d\"tex-span\"\u003e\u003ci\u003em\u003c/i\u003e\u003c/span\u003e integers \u003cspan class\u003d\"tex-span\"\u003e\u003ci\u003eb\u003c/i\u003e\u003csub class\u003d\"lower-index\"\u003e\u003ci\u003ei\u003c/i\u003e\u003c/sub\u003e\u003c/span\u003e (\u003cspan class\u003d\"tex-span\"\u003e1 ≤ \u003ci\u003eb\u003c/i\u003e\u003csub class\u003d\"lower-index\"\u003e\u003ci\u003ei\u003c/i\u003e\u003c/sub\u003e ≤ 2·10\u003csup class\u003d\"upper-index\"\u003e9\u003c/sup\u003e\u003c/span\u003e)\u0026nbsp;— the number of manapoints to use the \u003cspan class\u003d\"tex-span\"\u003e\u003ci\u003ei\u003c/i\u003e\u003c/span\u003e-th spell of the first type.\u003c/p\u003e\u003cp\u003eThere are \u003cspan class\u003d\"tex-span\"\u003e\u003ci\u003ek\u003c/i\u003e\u003c/span\u003e integers \u003cspan class\u003d\"tex-span\"\u003e\u003ci\u003ec\u003c/i\u003e\u003csub class\u003d\"lower-index\"\u003e\u003ci\u003ei\u003c/i\u003e\u003c/sub\u003e\u003c/span\u003e (\u003cspan class\u003d\"tex-span\"\u003e1 ≤ \u003ci\u003ec\u003c/i\u003e\u003csub class\u003d\"lower-index\"\u003e\u003ci\u003ei\u003c/i\u003e\u003c/sub\u003e ≤ \u003ci\u003en\u003c/i\u003e\u003c/span\u003e) in the fifth line\u0026nbsp;— the number of potions that will be immediately created if the \u003cspan class\u003d\"tex-span\"\u003e\u003ci\u003ei\u003c/i\u003e\u003c/span\u003e-th spell of the second type is used. It\u0027s guaranteed that \u003cspan class\u003d\"tex-span\"\u003e\u003ci\u003ec\u003c/i\u003e\u003csub class\u003d\"lower-index\"\u003e\u003ci\u003ei\u003c/i\u003e\u003c/sub\u003e\u003c/span\u003e are \u003cspan class\u003d\"tex-font-style-bf\"\u003enot decreasing\u003c/span\u003e, i.e. \u003cspan class\u003d\"tex-span\"\u003e\u003ci\u003ec\u003c/i\u003e\u003csub class\u003d\"lower-index\"\u003e\u003ci\u003ei\u003c/i\u003e\u003c/sub\u003e ≤ \u003ci\u003ec\u003c/i\u003e\u003csub class\u003d\"lower-index\"\u003e\u003ci\u003ej\u003c/i\u003e\u003c/sub\u003e\u003c/span\u003e if \u003cspan class\u003d\"tex-span\"\u003e\u003ci\u003ei\u003c/i\u003e \u0026lt; \u003ci\u003ej\u003c/i\u003e\u003c/span\u003e.\u003c/p\u003e\u003cp\u003eThe sixth line contains \u003cspan class\u003d\"tex-span\"\u003e\u003ci\u003ek\u003c/i\u003e\u003c/span\u003e integers \u003cspan class\u003d\"tex-span\"\u003e\u003ci\u003ed\u003c/i\u003e\u003csub class\u003d\"lower-index\"\u003e\u003ci\u003ei\u003c/i\u003e\u003c/sub\u003e\u003c/span\u003e (\u003cspan class\u003d\"tex-span\"\u003e1 ≤ \u003ci\u003ed\u003c/i\u003e\u003csub class\u003d\"lower-index\"\u003e\u003ci\u003ei\u003c/i\u003e\u003c/sub\u003e ≤ 2·10\u003csup class\u003d\"upper-index\"\u003e9\u003c/sup\u003e\u003c/span\u003e)\u0026nbsp;— the number of manapoints required to use the \u003cspan class\u003d\"tex-span\"\u003e\u003ci\u003ei\u003c/i\u003e\u003c/span\u003e-th spell of the second type. It\u0027s guaranteed that \u003cspan class\u003d\"tex-span\"\u003e\u003ci\u003ed\u003c/i\u003e\u003csub class\u003d\"lower-index\"\u003e\u003ci\u003ei\u003c/i\u003e\u003c/sub\u003e\u003c/span\u003e are \u003cspan class\u003d\"tex-font-style-bf\"\u003enot decreasing\u003c/span\u003e, i.e. \u003cspan class\u003d\"tex-span\"\u003e\u003ci\u003ed\u003c/i\u003e\u003csub class\u003d\"lower-index\"\u003e\u003ci\u003ei\u003c/i\u003e\u003c/sub\u003e ≤ \u003ci\u003ed\u003c/i\u003e\u003csub class\u003d\"lower-index\"\u003e\u003ci\u003ej\u003c/i\u003e\u003c/sub\u003e\u003c/span\u003e if \u003cspan class\u003d\"tex-span\"\u003e\u003ci\u003ei\u003c/i\u003e \u0026lt; \u003ci\u003ej\u003c/i\u003e\u003c/span\u003e.\u003c/p\u003e"}},{"title":"Output","value":{"format":"HTML","content":"\u003cp\u003ePrint one integer\u0026nbsp;— the minimum time one has to spent in order to prepare \u003cspan class\u003d\"tex-span\"\u003e\u003ci\u003en\u003c/i\u003e\u003c/span\u003e potions.\u003c/p\u003e"}},{"title":"Examples","value":{"format":"HTML","content":"\u003ctable class\u003d\u0027vjudge_sample\u0027\u003e\n\u003cthead\u003e\n \u003ctr\u003e\n \u003cth\u003eInput\u003c/th\u003e\n \u003cth\u003eOutput\u003c/th\u003e\n \u003c/tr\u003e\n\u003c/thead\u003e\n\u003ctbody\u003e\n \u003ctr\u003e\n \u003ctd\u003e\u003cpre\u003e20 3 2\n10 99\n2 4 3\n20 10 40\n4 15\n10 80\n\u003c/pre\u003e\u003c/td\u003e\n \u003ctd\u003e\u003cpre\u003e20\n\u003c/pre\u003e\u003c/td\u003e\n \u003c/tr\u003e\n\u003c/tbody\u003e\n\u003c/table\u003e\n"}},{"title":"","value":{"format":"HTML","content":"\u003ctable class\u003d\u0027vjudge_sample\u0027\u003e\n\u003cthead\u003e\n \u003ctr\u003e\n \u003cth\u003eInput\u003c/th\u003e\n \u003cth\u003eOutput\u003c/th\u003e\n \u003c/tr\u003e\n\u003c/thead\u003e\n\u003ctbody\u003e\n \u003ctr\u003e\n \u003ctd\u003e\u003cpre\u003e20 3 2\n10 99\n2 4 3\n200 100 400\n4 15\n100 800\n\u003c/pre\u003e\u003c/td\u003e\n \u003ctd\u003e\u003cpre\u003e200\n\u003c/pre\u003e\u003c/td\u003e\n \u003c/tr\u003e\n\u003c/tbody\u003e\n\u003c/table\u003e\n"}},{"title":"Note","value":{"format":"HTML","content":"\u003cp\u003eIn the first sample, the optimum answer is to use the second spell of the first type that costs \u003cspan class\u003d\"tex-span\"\u003e10\u003c/span\u003e manapoints. Thus, the preparation time of each potion changes to \u003cspan class\u003d\"tex-span\"\u003e4\u003c/span\u003e seconds. Also, Anton should use the second spell of the second type to instantly prepare \u003cspan class\u003d\"tex-span\"\u003e15\u003c/span\u003e potions spending \u003cspan class\u003d\"tex-span\"\u003e80\u003c/span\u003e manapoints. The total number of manapoints used is \u003cspan class\u003d\"tex-span\"\u003e10 + 80 \u003d 90\u003c/span\u003e, and the preparation time is \u003cspan class\u003d\"tex-span\"\u003e4·5 \u003d 20\u003c/span\u003e seconds (\u003cspan class\u003d\"tex-span\"\u003e15\u003c/span\u003e potions were prepared instantly, and the remaining \u003cspan class\u003d\"tex-span\"\u003e5\u003c/span\u003e will take \u003cspan class\u003d\"tex-span\"\u003e4\u003c/span\u003e seconds each).\u003c/p\u003e\u003cp\u003eIn the second sample, Anton can\u0027t use any of the spells, so he just prepares \u003cspan class\u003d\"tex-span\"\u003e20\u003c/span\u003e potions, spending \u003cspan class\u003d\"tex-span\"\u003e10\u003c/span\u003e seconds on each of them and the answer is \u003cspan class\u003d\"tex-span\"\u003e20·10 \u003d 200\u003c/span\u003e.\u003c/p\u003e"}}]}