{"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\n\u003cscript\u003e\n window.katexOptions \u003d {\n delimiters: [\n {left: \u0027$$$$$$\u0027, right: \u0027$$$$$$\u0027, display: true},\n {left: \u0027$$$\u0027, right: \u0027$$$\u0027, display: false},\n {left: \u0027$$\u0027, right: \u0027$$\u0027, display: true},\n {left: \u0027$\u0027, right: \u0027$\u0027, display: false}\n ]\n };\n\u003c/script\u003e\n","sections":[{"title":"","value":{"format":"HTML","content":"\u003cp\u003eMalek is a rich man. He also is very generous. That\u0027s why he decided to split his money between poor people. A charity institute knows \u003cspan class\u003d\"tex-span\"\u003e\u003ci\u003en\u003c/i\u003e\u003c/span\u003e poor people numbered from \u003cspan class\u003d\"tex-span\"\u003e1\u003c/span\u003e to \u003cspan class\u003d\"tex-span\"\u003e\u003ci\u003en\u003c/i\u003e\u003c/span\u003e. The institute gave Malek \u003cspan class\u003d\"tex-span\"\u003e\u003ci\u003eq\u003c/i\u003e\u003c/span\u003e recommendations. A recommendation is a segment of people like \u003cspan class\u003d\"tex-span\"\u003e[\u003ci\u003el\u003c/i\u003e, \u003ci\u003er\u003c/i\u003e]\u003c/span\u003e which means the institute recommended that Malek gives one dollar to every person whose number is in this segment.\u003c/p\u003e\u003cp\u003eHowever this charity has very odd rules about the recommendations. Because of those rules the recommendations are given in such a way that for every two recommendation \u003cspan class\u003d\"tex-span\"\u003e[\u003ci\u003ea\u003c/i\u003e, \u003ci\u003eb\u003c/i\u003e]\u003c/span\u003e and \u003cspan class\u003d\"tex-span\"\u003e[\u003ci\u003ec\u003c/i\u003e, \u003ci\u003ed\u003c/i\u003e]\u003c/span\u003e one of the following conditions holds: \u003c/p\u003e\u003cul\u003e \u003cli\u003e The two segments are completely disjoint. More formally either \u003cspan class\u003d\"tex-span\"\u003e\u003ci\u003ea\u003c/i\u003e ≤ \u003ci\u003eb\u003c/i\u003e \u0026lt; \u003ci\u003ec\u003c/i\u003e ≤ \u003ci\u003ed\u003c/i\u003e\u003c/span\u003e or \u003cspan class\u003d\"tex-span\"\u003e\u003ci\u003ec\u003c/i\u003e ≤ \u003ci\u003ed\u003c/i\u003e \u0026lt; \u003ci\u003ea\u003c/i\u003e ≤ \u003ci\u003eb\u003c/i\u003e\u003c/span\u003e \u003c/li\u003e\u003cli\u003e One of the two segments are inside another. More formally either \u003cspan class\u003d\"tex-span\"\u003e\u003ci\u003ea\u003c/i\u003e ≤ \u003ci\u003ec\u003c/i\u003e ≤ \u003ci\u003ed\u003c/i\u003e ≤ \u003ci\u003eb\u003c/i\u003e\u003c/span\u003e or \u003cspan class\u003d\"tex-span\"\u003e\u003ci\u003ec\u003c/i\u003e ≤ \u003ci\u003ea\u003c/i\u003e ≤ \u003ci\u003eb\u003c/i\u003e ≤ \u003ci\u003ed\u003c/i\u003e\u003c/span\u003e. \u003c/li\u003e\u003c/ul\u003e\u003cp\u003eThe \u003cspan class\u003d\"tex-font-style-underline\"\u003egoodness\u003c/span\u003e of a charity is the value of maximum money a person has after Malek finishes giving his money. The institute knows for each recommendation what is the probability that Malek will accept it. They want to know the expected value of \u003cspan class\u003d\"tex-font-style-underline\"\u003egoodness\u003c/span\u003e of this charity. So they asked you for help.\u003c/p\u003e\u003cp\u003eYou have been given the list of recommendations and for each recommendation the probability of it being accepted by Malek. You have also been given how much money each person initially has. You must find the expected value of \u003cspan class\u003d\"tex-font-style-underline\"\u003egoodness\u003c/span\u003e.\u003c/p\u003e"}},{"title":"Input","value":{"format":"HTML","content":"\u003cp\u003eIn the first line two space-separated integers \u003cspan class\u003d\"tex-span\"\u003e\u003ci\u003en\u003c/i\u003e, \u003ci\u003eq\u003c/i\u003e\u003c/span\u003e (\u003cspan class\u003d\"tex-span\"\u003e1 ≤ \u003ci\u003en\u003c/i\u003e ≤ 10\u003csup class\u003d\"upper-index\"\u003e5\u003c/sup\u003e\u003c/span\u003e, \u003cspan class\u003d\"tex-span\"\u003e1 ≤ \u003ci\u003eq\u003c/i\u003e ≤ 5000\u003c/span\u003e) are given.\u003c/p\u003e\u003cp\u003eIn the second line \u003cspan class\u003d\"tex-span\"\u003e\u003ci\u003en\u003c/i\u003e\u003c/span\u003e space-separated integers \u003cspan class\u003d\"tex-span\"\u003e\u003ci\u003ea\u003c/i\u003e\u003csub class\u003d\"lower-index\"\u003e1\u003c/sub\u003e, \u003ci\u003ea\u003c/i\u003e\u003csub class\u003d\"lower-index\"\u003e2\u003c/sub\u003e, ..., \u003ci\u003ea\u003c/i\u003e\u003csub class\u003d\"lower-index\"\u003e\u003ci\u003en\u003c/i\u003e\u003c/sub\u003e\u003c/span\u003e (\u003cspan class\u003d\"tex-span\"\u003e0 ≤ \u003ci\u003ea\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) are given meaning that person number \u003cspan class\u003d\"tex-span\"\u003e\u003ci\u003ei\u003c/i\u003e\u003c/span\u003e initially has \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 dollars. \u003c/p\u003e\u003cp\u003eEach of the next \u003cspan class\u003d\"tex-span\"\u003e\u003ci\u003eq\u003c/i\u003e\u003c/span\u003e lines contains three space-separated numbers \u003cspan class\u003d\"tex-span\"\u003e\u003ci\u003el\u003c/i\u003e\u003csub class\u003d\"lower-index\"\u003e\u003ci\u003ei\u003c/i\u003e\u003c/sub\u003e, \u003ci\u003er\u003c/i\u003e\u003csub class\u003d\"lower-index\"\u003e\u003ci\u003ei\u003c/i\u003e\u003c/sub\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\"\u003e1 ≤ \u003ci\u003el\u003c/i\u003e\u003csub class\u003d\"lower-index\"\u003e\u003ci\u003ei\u003c/i\u003e\u003c/sub\u003e ≤ \u003ci\u003er\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, \u003cspan class\u003d\"tex-span\"\u003e0 ≤ \u003ci\u003ep\u003c/i\u003e ≤ 1\u003c/span\u003e) where \u003cspan class\u003d\"tex-span\"\u003e\u003ci\u003el\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\u003er\u003c/i\u003e\u003csub class\u003d\"lower-index\"\u003e\u003ci\u003ei\u003c/i\u003e\u003c/sub\u003e\u003c/span\u003e are two integers describing the segment of recommendation and \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 is a real number given with exactly three digits after decimal point which is equal to probability of Malek accepting this recommendation.\u003c/p\u003e\u003cp\u003eNote that a segment may appear several times in recommendations.\u003c/p\u003e"}},{"title":"Output","value":{"format":"HTML","content":"\u003cp\u003eOutput the sought value. Your answer will be considered correct if its absolute or relative error is less than \u003cspan class\u003d\"tex-span\"\u003e10\u003csup class\u003d\"upper-index\"\u003e - 6\u003c/sup\u003e\u003c/span\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\u003e5 2\n1 7 2 4 3\n1 3 0.500\n2 2 0.500\n\u003c/pre\u003e\u003c/td\u003e\n \u003ctd\u003e\u003cpre\u003e8.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\u003e5 2\n281 280 279 278 282\n1 4 1.000\n1 4 0.000\n\u003c/pre\u003e\u003c/td\u003e\n \u003ctd\u003e\u003cpre\u003e282.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\u003e3 5\n1 2 3\n1 3 0.500\n2 2 0.250\n1 2 0.800\n1 1 0.120\n2 2 0.900\n\u003c/pre\u003e\u003c/td\u003e\n \u003ctd\u003e\u003cpre\u003e4.465000000\n\u003c/pre\u003e\u003c/td\u003e\n \u003c/tr\u003e\n\u003c/tbody\u003e\n\u003c/table\u003e\n"}}]}