{"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\u003eI guess there\u0027s not much point in reminding you that Nvodsk winters aren\u0027t exactly hot. That increased the popularity of the public transport dramatically. The route of bus \u003cspan class\u003d\"tex-span\"\u003e62\u003c/span\u003e has exactly \u003cspan class\u003d\"tex-span\"\u003e\u003ci\u003en\u003c/i\u003e\u003c/span\u003e stops (stop \u003cspan class\u003d\"tex-span\"\u003e1\u003c/span\u003e goes first on its way and stop \u003cspan class\u003d\"tex-span\"\u003e\u003ci\u003en\u003c/i\u003e\u003c/span\u003e goes last). The stops are positioned on a straight line and their coordinates are \u003cspan class\u003d\"tex-span\"\u003e0 \u003d \u003ci\u003ex\u003c/i\u003e\u003csub class\u003d\"lower-index\"\u003e1\u003c/sub\u003e \u0026lt; \u003ci\u003ex\u003c/i\u003e\u003csub class\u003d\"lower-index\"\u003e2\u003c/sub\u003e \u0026lt; ... \u0026lt; \u003ci\u003ex\u003c/i\u003e\u003csub class\u003d\"lower-index\"\u003e\u003ci\u003en\u003c/i\u003e\u003c/sub\u003e\u003c/span\u003e. \u003c/p\u003e\u003cp\u003eEach day exactly \u003cspan class\u003d\"tex-span\"\u003e\u003ci\u003em\u003c/i\u003e\u003c/span\u003e people use bus \u003cspan class\u003d\"tex-span\"\u003e62\u003c/span\u003e. For each person we know the number of the stop where he gets on the bus and the number of the stop where he gets off the bus. A ticket from stop \u003cspan class\u003d\"tex-span\"\u003e\u003ci\u003ea\u003c/i\u003e\u003c/span\u003e to stop \u003cspan class\u003d\"tex-span\"\u003e\u003ci\u003eb\u003c/i\u003e\u003c/span\u003e (\u003cspan class\u003d\"tex-span\"\u003e\u003ci\u003ea\u003c/i\u003e \u0026lt; \u003ci\u003eb\u003c/i\u003e\u003c/span\u003e) costs \u003cspan class\u003d\"tex-span\"\u003e\u003ci\u003ex\u003c/i\u003e\u003csub class\u003d\"lower-index\"\u003e\u003ci\u003eb\u003c/i\u003e\u003c/sub\u003e - \u003ci\u003ex\u003c/i\u003e\u003csub class\u003d\"lower-index\"\u003e\u003ci\u003ea\u003c/i\u003e\u003c/sub\u003e\u003c/span\u003e rubles. However, the conductor can choose no more than one segment NOT TO SELL a ticket for. We mean that conductor should choose C and D (С \u0026lt;\u003d D) and sell a ticket for the segments [\u003cspan class\u003d\"tex-span\"\u003e\u003ci\u003eA\u003c/i\u003e\u003c/span\u003e, \u003cspan class\u003d\"tex-span\"\u003e\u003ci\u003eC\u003c/i\u003e\u003c/span\u003e] and [\u003cspan class\u003d\"tex-span\"\u003e\u003ci\u003eD\u003c/i\u003e\u003c/span\u003e, \u003cspan class\u003d\"tex-span\"\u003e\u003ci\u003eB\u003c/i\u003e\u003c/span\u003e], or not sell the ticket at all. The conductor and the passenger divide the saved money between themselves equally. The conductor\u0027s \"untaxed income\" is sometimes interrupted by inspections that take place as the bus drives on some segment of the route located between two consecutive stops. The inspector fines the conductor by \u003cspan class\u003d\"tex-span\"\u003e\u003ci\u003ec\u003c/i\u003e\u003c/span\u003e rubles for each passenger who doesn\u0027t have the ticket for this route\u0027s segment.\u003c/p\u003e\u003cp\u003eYou know the coordinated of all stops \u003cspan class\u003d\"tex-span\"\u003e\u003ci\u003ex\u003c/i\u003e\u003csub class\u003d\"lower-index\"\u003e\u003ci\u003ei\u003c/i\u003e\u003c/sub\u003e\u003c/span\u003e; the numbers of stops where the \u003cspan class\u003d\"tex-span\"\u003e\u003ci\u003ei\u003c/i\u003e\u003c/span\u003e-th passenger gets on and off, \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 and \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\"\u003e\u003ci\u003ea\u003c/i\u003e\u003csub class\u003d\"lower-index\"\u003e\u003ci\u003ei\u003c/i\u003e\u003c/sub\u003e \u0026lt; \u003ci\u003eb\u003c/i\u003e\u003csub class\u003d\"lower-index\"\u003e\u003ci\u003ei\u003c/i\u003e\u003c/sub\u003e\u003c/span\u003e); the fine \u003cspan class\u003d\"tex-span\"\u003e\u003ci\u003ec\u003c/i\u003e\u003c/span\u003e; and also \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 — the probability of inspection on segment between the \u003cspan class\u003d\"tex-span\"\u003e\u003ci\u003ei\u003c/i\u003e\u003c/span\u003e-th and the \u003cspan class\u003d\"tex-span\"\u003e\u003ci\u003ei\u003c/i\u003e + 1\u003c/span\u003e-th stop. The conductor asked you to help him make a plan of selling tickets that maximizes the mathematical expectation of his profit.\u003c/p\u003e"}},{"title":"Input","value":{"format":"HTML","content":"\u003cp\u003eThe first line 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 and \u003cspan class\u003d\"tex-span\"\u003e\u003ci\u003ec\u003c/i\u003e\u003c/span\u003e (\u003cspan class\u003d\"tex-span\"\u003e2 ≤ \u003ci\u003en\u003c/i\u003e ≤ 150 000\u003c/span\u003e, \u003cspan class\u003d\"tex-span\"\u003e1 ≤ \u003ci\u003em\u003c/i\u003e ≤ 300 000\u003c/span\u003e, \u003cspan class\u003d\"tex-span\"\u003e1 ≤ \u003ci\u003ec\u003c/i\u003e ≤ 10 000\u003c/span\u003e).\u003c/p\u003e\u003cp\u003eThe next line contains \u003cspan class\u003d\"tex-span\"\u003e\u003ci\u003en\u003c/i\u003e\u003c/span\u003e integers \u003cspan class\u003d\"tex-span\"\u003e\u003ci\u003ex\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\u003ex\u003c/i\u003e\u003csub class\u003d\"lower-index\"\u003e\u003ci\u003ei\u003c/i\u003e\u003c/sub\u003e ≤ 10\u003csup class\u003d\"upper-index\"\u003e9\u003c/sup\u003e\u003c/span\u003e, \u003cspan class\u003d\"tex-span\"\u003e\u003ci\u003ex\u003c/i\u003e\u003csub class\u003d\"lower-index\"\u003e1\u003c/sub\u003e \u003d 0\u003c/span\u003e, \u003cspan class\u003d\"tex-span\"\u003e\u003ci\u003ex\u003c/i\u003e\u003csub class\u003d\"lower-index\"\u003e\u003ci\u003ei\u003c/i\u003e\u003c/sub\u003e \u0026lt; \u003ci\u003ex\u003c/i\u003e\u003csub class\u003d\"lower-index\"\u003e\u003ci\u003ei\u003c/i\u003e + 1\u003c/sub\u003e\u003c/span\u003e) — the coordinates of the stops on the bus\u0027s route.\u003c/p\u003e\u003cp\u003eThe third line contains \u003cspan class\u003d\"tex-span\"\u003e\u003ci\u003en\u003c/i\u003e - 1\u003c/span\u003e 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 ≤ 100\u003c/span\u003e) — the probability of inspection in percents on the segment between stop \u003cspan class\u003d\"tex-span\"\u003e\u003ci\u003ei\u003c/i\u003e\u003c/span\u003e and stop \u003cspan class\u003d\"tex-span\"\u003e\u003ci\u003ei\u003c/i\u003e + 1\u003c/span\u003e.\u003c/p\u003e\u003cp\u003eThen follow \u003cspan class\u003d\"tex-span\"\u003e\u003ci\u003em\u003c/i\u003e\u003c/span\u003e lines that describe the bus\u0027s passengers. Each line contains exactly two 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 and \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\u003ea\u003c/i\u003e\u003csub class\u003d\"lower-index\"\u003e\u003ci\u003ei\u003c/i\u003e\u003c/sub\u003e \u0026lt; \u003ci\u003eb\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) — the numbers of stops where the \u003cspan class\u003d\"tex-span\"\u003e\u003ci\u003ei\u003c/i\u003e\u003c/span\u003e-th passenger gets on and off.\u003c/p\u003e"}},{"title":"Output","value":{"format":"HTML","content":"\u003cp\u003ePrint the single real number — the maximum expectation of the conductor\u0027s profit. Your answer will be considered correct if its absolute or relative error does not exceed \u003cspan class\u003d\"tex-span\"\u003e10\u003csup class\u003d\"upper-index\"\u003e - 6\u003c/sup\u003e\u003c/span\u003e. \u003c/p\u003e\u003cp\u003eNamely: let\u0027s assume that your answer is \u003cspan class\u003d\"tex-span\"\u003e\u003ci\u003ea\u003c/i\u003e\u003c/span\u003e, and the answer of the jury is \u003cspan class\u003d\"tex-span\"\u003e\u003ci\u003eb\u003c/i\u003e\u003c/span\u003e. The checker program will consider your answer correct, if \u003cimg align\u003d\"middle\" class\u003d\"tex-formula\" src\u003d\"CDN_BASE_URL/a804da1528e75d5966b337038e5ebb1f?v\u003d1715603953\" style\u003d\"max-width: 100.0%;max-height: 100.0%;\"\u003e.\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\u003e3 3 10\n0 10 100\n100 0\n1 2\n2 3\n1 3\n\u003c/pre\u003e\u003c/td\u003e\n \u003ctd\u003e\u003cpre\u003e90.000000000\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 8 187\n0 10 30 70 150 310 630 1270 2550 51100\n13 87 65 0 100 44 67 3 4\n1 10\n2 9\n3 8\n1 5\n6 10\n2 7\n4 10\n4 5\n\u003c/pre\u003e\u003c/td\u003e\n \u003ctd\u003e\u003cpre\u003e76859.990000000\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\u003eA comment to the first sample:\u003c/p\u003e\u003cp\u003eThe first and third passengers get tickets from stop \u003cspan class\u003d\"tex-span\"\u003e1\u003c/span\u003e to stop \u003cspan class\u003d\"tex-span\"\u003e2\u003c/span\u003e. The second passenger doesn\u0027t get a ticket. There always is inspection on the segment \u003cspan class\u003d\"tex-span\"\u003e1\u003c/span\u003e-\u003cspan class\u003d\"tex-span\"\u003e2\u003c/span\u003e but both passengers have the ticket for it. There never is an inspection on the segment \u003cspan class\u003d\"tex-span\"\u003e2\u003c/span\u003e-\u003cspan class\u003d\"tex-span\"\u003e3\u003c/span\u003e, that\u0027s why the second passenger gets away with the cheating. Our total profit is \u003cspan class\u003d\"tex-span\"\u003e(0 + 90 / 2 + 90 / 2) \u003d 90\u003c/span\u003e.\u003c/p\u003e"}}]}