{"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\u003eMobilization is a brand new strategy game in which you are\n required to mobilize an army. The army can consist of different\n types of troops, each of which has a cost, health, and potency.\n You can acquire any combination of the troop types, even\n fractional, such that the total cost is no more than the amount\n you have to spend. The efficacy of the army is equal to its\n total health value multiplied by its total potency. What is the\n greatest efficacy you can achieve with the given purchasing\n constraints?\u003c/p\u003e\n \u003cp\u003eYou may assume that there are always sufficient troops\n available to buy as many as you want (subject to the total\n constraint).\u003c/p\u003e\n \u003ch2\u003eInput\u003c/h2\u003e\n \u003cp\u003eThe first line will contain two integers, the number of\n different types of troops \u003cspan class\u003d\"tex2jax_process\"\u003e$n$\u003c/span\u003e (\u003cspan class\u003d\"tex2jax_process\"\u003e$1\n \\le n \\le 30\\, 000$\u003c/span\u003e and the total budget you have to\n spend \u003cspan class\u003d\"tex2jax_process\"\u003e$b$\u003c/span\u003e (\u003cspan class\u003d\"tex2jax_process\"\u003e$1 \\le b \\le 100\\, 000$\u003c/span\u003e).\u003c/p\u003e\n \u003cp\u003eFollowing this will be \u003cspan class\u003d\"tex2jax_process\"\u003e$n$\u003c/span\u003e lines, each with three values for\n this troop type: an integer value of its unit cost \u003cspan class\u003d\"tex2jax_process\"\u003e$c$\u003c/span\u003e (\u003cspan class\u003d\"tex2jax_process\"\u003e$1\n \\le c \\le 100\\, 000$\u003c/span\u003e, a real value of its unit health\n \u003cspan class\u003d\"tex2jax_process\"\u003e$h$\u003c/span\u003e (\u003cspan class\u003d\"tex2jax_process\"\u003e$0 \\le h \\le 1$\u003c/span\u003e), and a real value of\n its unit potency \u003cspan class\u003d\"tex2jax_process\"\u003e$p$\u003c/span\u003e\n (\u003cspan class\u003d\"tex2jax_process\"\u003e$0 \\le p \\le 1$\u003c/span\u003e). The\n real values may contain up to \u003cspan class\u003d\"tex2jax_process\"\u003e$20$\u003c/span\u003e digits after the decimal\n point.\u003c/p\u003e\n \u003ch2\u003eOutput\u003c/h2\u003e\n \u003cp\u003eThe output is a line containing one number, the greatest\n possible efficacy expressed with a relative or absolute error\n less than \u003cspan class\u003d\"tex2jax_process\"\u003e$0.005$\u003c/span\u003e.\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\u003e4 100000\n300 1 0.02\n500 0.2 1\n250 0.3 0.1\n1000 1 0.1\n\u003c/pre\u003e\u003c/td\u003e\n \u003ctd\u003e\u003cpre\u003e19436.05\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\u003e2 100\n1 0.1 1\n1 1 0.1\n\u003c/pre\u003e\u003c/td\u003e\n \u003ctd\u003e\u003cpre\u003e3025.00\n\u003c/pre\u003e\u003c/td\u003e\n \u003c/tr\u003e\n\u003c/tbody\u003e\n\u003c/table\u003e\n\u003c/body\u003e\n "}}]}