{"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\u003e\u003cspan class\u003d\"tex-font-style-it\"\u003eThis problem consists of three subproblems: for solving subproblem F1 you will receive 8 points, for solving subproblem F2 you will receive 15 points, and for solving subproblem F3 you will receive 10 points.\u003c/span\u003e\u003c/p\u003e\u003cp\u003eManao has developed a model to predict the stock price of a company over the next \u003cspan class\u003d\"tex-span\"\u003e\u003ci\u003en\u003c/i\u003e\u003c/span\u003e days and wants to design a profit-maximizing trading algorithm to make use of these predictions. Unfortunately, Manao\u0027s trading account has the following restrictions: \u003c/p\u003e\u003cul\u003e \u003cli\u003e It only allows owning either zero or one shares of stock at a time; \u003c/li\u003e\u003cli\u003e It only allows buying or selling a share of this stock once per day; \u003c/li\u003e\u003cli\u003e It allows a maximum of \u003cspan class\u003d\"tex-span\"\u003e\u003ci\u003ek\u003c/i\u003e\u003c/span\u003e buy orders over the next \u003cspan class\u003d\"tex-span\"\u003e\u003ci\u003en\u003c/i\u003e\u003c/span\u003e days; \u003c/li\u003e\u003c/ul\u003e\u003cp\u003eFor the purposes of this problem, we define a \u003cspan class\u003d\"tex-font-style-underline\"\u003etrade\u003c/span\u003e to a be the act of buying one share of stock on day \u003cspan class\u003d\"tex-span\"\u003e\u003ci\u003ei\u003c/i\u003e\u003c/span\u003e, then holding the stock until some day \u003cspan class\u003d\"tex-span\"\u003e\u003ci\u003ej\u003c/i\u003e \u0026gt; \u003ci\u003ei\u003c/i\u003e\u003c/span\u003e at which point the share is sold. To restate the above constraints, Manao is permitted to make at most \u003cspan class\u003d\"tex-span\"\u003e\u003ci\u003ek\u003c/i\u003e\u003c/span\u003e non-overlapping trades during the course of an \u003cspan class\u003d\"tex-span\"\u003e\u003ci\u003en\u003c/i\u003e\u003c/span\u003e-day trading period for which Manao\u0027s model has predictions about the stock price.\u003c/p\u003e\u003cp\u003eEven though these restrictions limit the amount of profit Manao can make compared to what would be achievable with an unlimited number of trades or the ability to hold more than one share at a time, Manao still has the potential to make a lot of money because Manao\u0027s model perfectly predicts the daily price of the stock. For example, using this model, Manao could wait until the price is low, then buy one share and hold until the price reaches a high value, then sell for a profit, and repeat this process up to \u003cspan class\u003d\"tex-span\"\u003e\u003ci\u003ek\u003c/i\u003e\u003c/span\u003e times until \u003cspan class\u003d\"tex-span\"\u003e\u003ci\u003en\u003c/i\u003e\u003c/span\u003e days have passed.\u003c/p\u003e\u003cp\u003eNevertheless, Manao is not satisfied by having a merely good trading algorithm, and wants to develop an optimal strategy for trading subject to these constraints. Help Manao achieve this goal by writing a program that will determine when to buy and sell stock to achieve the greatest possible profit during the \u003cspan class\u003d\"tex-span\"\u003e\u003ci\u003en\u003c/i\u003e\u003c/span\u003e-day trading period subject to the above constraints.\u003c/p\u003e"}},{"title":"Input","value":{"format":"HTML","content":"\u003cp\u003eThe first line contains two integers \u003cspan class\u003d\"tex-span\"\u003e\u003ci\u003en\u003c/i\u003e\u003c/span\u003e and \u003cspan class\u003d\"tex-span\"\u003e\u003ci\u003ek\u003c/i\u003e\u003c/span\u003e, separated by a single space, with \u003cimg align\u003d\"middle\" class\u003d\"tex-formula\" src\u003d\"CDN_BASE_URL/45427b377d46a16d395e004953251f52?v\u003d1715734465\" style\u003d\"max-width: 100.0%;max-height: 100.0%;\"\u003e. The \u003cspan class\u003d\"tex-span\"\u003e\u003ci\u003ei\u003c/i\u003e\u003c/span\u003e-th of the following \u003cspan class\u003d\"tex-span\"\u003e\u003ci\u003en\u003c/i\u003e\u003c/span\u003e lines contains a single integer \u003cspan class\u003d\"tex-span\"\u003e\u003ci\u003ep\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\"\u003e0 ≤ \u003ci\u003ep\u003c/i\u003e\u003csub class\u003d\"lower-index\"\u003e\u003ci\u003ei\u003c/i\u003e\u003c/sub\u003e ≤ 10\u003csup class\u003d\"upper-index\"\u003e12\u003c/sup\u003e\u003c/span\u003e), where \u003cspan class\u003d\"tex-span\"\u003e\u003ci\u003ep\u003c/i\u003e\u003csub class\u003d\"lower-index\"\u003e\u003ci\u003ei\u003c/i\u003e\u003c/sub\u003e\u003c/span\u003e represents the price at which someone can either buy or sell one share of stock on day \u003cspan class\u003d\"tex-span\"\u003e\u003ci\u003ei\u003c/i\u003e\u003c/span\u003e.\u003c/p\u003e\u003cp\u003e\u003cspan class\u003d\"tex-font-style-it\"\u003eThe problem consists of three subproblems. The subproblems have different constraints on the input. You will get some score for the correct submission of the subproblem. The description of the subproblems follows.\u003c/span\u003e\u003c/p\u003e\u003cul\u003e \u003cli\u003e In subproblem F1 (8 points), \u003cspan class\u003d\"tex-span\"\u003e\u003ci\u003en\u003c/i\u003e\u003c/span\u003e will be between \u003cspan class\u003d\"tex-span\"\u003e1\u003c/span\u003e and \u003cspan class\u003d\"tex-span\"\u003e3000\u003c/span\u003e, inclusive. \u003c/li\u003e\u003cli\u003e In subproblem F2 (15 points), \u003cspan class\u003d\"tex-span\"\u003e\u003ci\u003en\u003c/i\u003e\u003c/span\u003e will be between \u003cspan class\u003d\"tex-span\"\u003e1\u003c/span\u003e and \u003cspan class\u003d\"tex-span\"\u003e100000\u003c/span\u003e, inclusive. \u003c/li\u003e\u003cli\u003e In subproblem F3 (10 points), \u003cspan class\u003d\"tex-span\"\u003e\u003ci\u003en\u003c/i\u003e\u003c/span\u003e will be between \u003cspan class\u003d\"tex-span\"\u003e1\u003c/span\u003e and \u003cspan class\u003d\"tex-span\"\u003e4000000\u003c/span\u003e, inclusive. \u003c/li\u003e\u003c/ul\u003e"}},{"title":"Output","value":{"format":"HTML","content":"\u003cp\u003eFor this problem, the program will only report the amount of the optimal profit, rather than a list of trades that can achieve this profit.\u003c/p\u003e\u003cp\u003eTherefore, the program should print one line containing a single integer, the maximum profit Manao can achieve over the next \u003cspan class\u003d\"tex-span\"\u003e\u003ci\u003en\u003c/i\u003e\u003c/span\u003e days with the constraints of starting with no shares on the first day of trading, always owning either zero or one shares of stock, and buying at most \u003cspan class\u003d\"tex-span\"\u003e\u003ci\u003ek\u003c/i\u003e\u003c/span\u003e shares over the course of the \u003cspan class\u003d\"tex-span\"\u003e\u003ci\u003en\u003c/i\u003e\u003c/span\u003e-day trading period.\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\u003e10 2\n2\n7\n3\n9\n8\n7\n9\n7\n1\n9\n\u003c/pre\u003e\u003c/td\u003e\n \u003ctd\u003e\u003cpre\u003e15\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\u003e10 5\n2\n7\n3\n9\n8\n7\n9\n7\n1\n9\n\u003c/pre\u003e\u003c/td\u003e\n \u003ctd\u003e\u003cpre\u003e21\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 example, the best trade overall is to buy at a price of \u003cspan class\u003d\"tex-span\"\u003e1\u003c/span\u003e on day 9 and sell at a price of \u003cspan class\u003d\"tex-span\"\u003e9\u003c/span\u003e on day 10 and the second best trade overall is to buy at a price of \u003cspan class\u003d\"tex-span\"\u003e2\u003c/span\u003e on day 1 and sell at a price of \u003cspan class\u003d\"tex-span\"\u003e9\u003c/span\u003e on day 4. Since these two trades do not overlap, both can be made and the profit is the sum of the profits of the two trades. Thus the trade strategy looks like this: \u003c/p\u003e\u003cpre class\u003d\"verbatim\"\u003e\u003cbr\u003e2 | 7 | 3 | 9 | 8 | 7 | 9 | 7 | 1 | 9\u003cbr\u003ebuy | | | sell | | | | | buy | sell\u003cbr\u003e\u003c/pre\u003e\u003cp\u003eThe total profit is then \u003cspan class\u003d\"tex-span\"\u003e(9 - 2) + (9 - 1) \u003d 15\u003c/span\u003e.\u003c/p\u003e\u003cp\u003eIn the second example, even though Manao is allowed up to 5 trades there are only 4 profitable trades available. Making a fifth trade would cost Manao money so he only makes the following 4: \u003c/p\u003e\u003cpre class\u003d\"verbatim\"\u003e\u003cbr\u003e2 | 7 | 3 | 9 | 8 | 7 | 9 | 7 | 1 | 9\u003cbr\u003ebuy | sell | buy | sell | | buy | sell | | buy | sell\u003cbr\u003e\u003c/pre\u003e\u003cp\u003eThe total profit is then \u003cspan class\u003d\"tex-span\"\u003e(7 - 2) + (9 - 3) + (9 - 7) + (9 - 1) \u003d 21\u003c/span\u003e.\u003c/p\u003e"}}]}