{"trustable":true,"prependHtml":"\u003cstyle type\u003d\"text/css\"\u003e\n div.illustration {\n float: right;\n padding-left: 20px;\n }\n div.illustration .illustration {\n width: 100%;\n border-radius: 4px;\n }\n pre {\n display: block;\n margin: 0 0 10px;\n font-size: 13px;\n line-height: 1.42857143;\n color: #333;\n word-break: break-all;\n word-wrap: break-word;\n }\n\u003c/style\u003e\n\u003cscript\u003e\n window.katexOptions \u003d {\n delimiters: [\n {left: \u0027\\\\[\u0027, right: \u0027\\\\]\u0027, display: true}\n ]\n };\n\u003c/script\u003e\n","sections":[{"title":"","value":{"format":"HTML","content":"\n \u003cp\u003eOlivia runs a very famous and profitable smoothie stand. On\n any given day, she will always sell out (that is, she will sell\n as many smoothies as she has ingredients to make), regardless\n of what smoothie recipe she offers. Therefore, to simplify\n things, she has decided she will only make one type of smoothie\n per day. Now she has come to you to help her decide which of\n her recipes she should use today, given the ingredients she has\n on hand and the sale price of each type of smoothie.\u003c/p\u003e\n \u003ch2\u003eInput\u003c/h2\u003e\n \u003cp\u003eThe first line contains two integers \u003cspan class\u003d\"tex2jax_process\"\u003e$k$\u003c/span\u003e and \u003cspan class\u003d\"tex2jax_process\"\u003e$r$\u003c/span\u003e, separated by a space. The value\n \u003cspan class\u003d\"tex2jax_process\"\u003e$k$\u003c/span\u003e is the number of\n different ingredients Olivia uses in her smoothies and\n \u003cspan class\u003d\"tex2jax_process\"\u003e$r$\u003c/span\u003e is the number of\n different recipes she makes. You may assume \u003cspan class\u003d\"tex2jax_process\"\u003e$1\\leq k\\leq 100\\, 000$\u003c/span\u003e, \u003cspan class\u003d\"tex2jax_process\"\u003e$1\\leq r\\leq 100\\, 000$\u003c/span\u003e, and\n \u003cspan class\u003d\"tex2jax_process\"\u003e$1\\leq kr\\leq 100\\, 000$\u003c/span\u003e.\n The second line contains \u003cspan class\u003d\"tex2jax_process\"\u003e$k$\u003c/span\u003e integers, which represent the\n amount of each ingredient she currently has on hand. This is\n followed by \u003cspan class\u003d\"tex2jax_process\"\u003e$r$\u003c/span\u003e lines,\n each of which represents a recipe. On each such line, the first\n \u003cspan class\u003d\"tex2jax_process\"\u003e$k$\u003c/span\u003e space-separated\n integers represent the amount of each ingredient used in that\n recipe. This is followed by one integer representing the price\n charged for one smoothie of that recipe.\u003c/p\u003e\n \u003cp\u003eYou may assume that all values, except possibly \u003cspan class\u003d\"tex2jax_process\"\u003e$k$\u003c/span\u003e and \u003cspan class\u003d\"tex2jax_process\"\u003e$r$\u003c/span\u003e, are nonnegative integers less\n than or equal to \u003cspan class\u003d\"tex2jax_process\"\u003e$10^4$\u003c/span\u003e.\n It is guaranteed that each recipe uses at least one\n ingredient.\u003c/p\u003e\n \u003ch2\u003eOutput\u003c/h2\u003e\n \u003cp\u003eOutput the largest total sales revenue that can be obtained\n by choosing a single recipe and making as many of that recipe\n as possible.\u003c/p\u003e\n \u003ch2\u003eSample 1\u003c/h2\u003e\u003cbody\u003e\u003ctable class\u003d\"vjudge_sample\"\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\u003e3 2\n5 10 10\n1 4 1 5\n3 3 3 3\n\u003c/pre\u003e\u003c/td\u003e\n \u003ctd\u003e\u003cpre\u003e10\n\u003c/pre\u003e\u003c/td\u003e\n \u003c/tr\u003e\n\u003c/tbody\u003e\n\u003c/table\u003e\n\u003c/body\u003e\n \u003ch2\u003eSample 2\u003c/h2\u003e\u003cbody\u003e\u003ctable class\u003d\"vjudge_sample\"\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\u003e4 3\n10 9 8 7\n0 1 2 4 10\n3 1 1 2 4\n2 0 3 3 5\n\u003c/pre\u003e\u003c/td\u003e\n \u003ctd\u003e\u003cpre\u003e12\n\u003c/pre\u003e\u003c/td\u003e\n \u003c/tr\u003e\n\u003c/tbody\u003e\n\u003c/table\u003e\n\u003c/body\u003e\n "}}]}