{"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\u003eYou are going to work in Codeforces as an intern in a team of \u003cspan class\u003d\"tex-span\"\u003e\u003ci\u003en\u003c/i\u003e\u003c/span\u003e engineers, numbered \u003cspan class\u003d\"tex-span\"\u003e1\u003c/span\u003e through \u003cspan class\u003d\"tex-span\"\u003e\u003ci\u003en\u003c/i\u003e\u003c/span\u003e. You want to give each engineer a souvenir: a T-shirt from your country (T-shirts are highly desirable in Codeforces). Unfortunately you don\u0027t know the size of the T-shirt each engineer fits in. There are \u003cspan class\u003d\"tex-span\"\u003e\u003ci\u003em\u003c/i\u003e\u003c/span\u003e different sizes, numbered \u003cspan class\u003d\"tex-span\"\u003e1\u003c/span\u003e through \u003cspan class\u003d\"tex-span\"\u003e\u003ci\u003em\u003c/i\u003e\u003c/span\u003e, and each engineer will fit in a T-shirt of exactly one size.\u003c/p\u003e\u003cp\u003eYou don\u0027t know the engineers\u0027 exact sizes, so you asked your friend, Gerald. Unfortunately, he wasn\u0027t able to obtain the exact sizes either, but he managed to obtain for each engineer \u003cspan class\u003d\"tex-span\"\u003e\u003ci\u003ei\u003c/i\u003e\u003c/span\u003e and for all sizes \u003cspan class\u003d\"tex-span\"\u003e\u003ci\u003ej\u003c/i\u003e\u003c/span\u003e, the probability that the size of the T-shirt that fits engineer \u003cspan class\u003d\"tex-span\"\u003e\u003ci\u003ei\u003c/i\u003e\u003c/span\u003e is \u003cspan class\u003d\"tex-span\"\u003e\u003ci\u003ej\u003c/i\u003e\u003c/span\u003e.\u003c/p\u003e\u003cp\u003eSince you\u0027re planning to give each engineer one T-shirt, you are going to bring with you exactly \u003cspan class\u003d\"tex-span\"\u003e\u003ci\u003en\u003c/i\u003e\u003c/span\u003e T-shirts. For those \u003cspan class\u003d\"tex-span\"\u003e\u003ci\u003en\u003c/i\u003e\u003c/span\u003e T-shirts, you can bring any combination of sizes (you can bring multiple T-shirts with the same size too!). You don\u0027t know the sizes of T-shirts for each engineer when deciding what sizes to bring, so you have to pick this combination based only on the probabilities given by your friend, Gerald. \u003c/p\u003e\u003cp\u003eYour task is to maximize the expected number of engineers that receive a T-shirt of his size. \u003c/p\u003e\u003cp\u003eThis is defined more formally as follows. When you finally arrive at the office, you will ask each engineer his T-shirt size. Then, if you still have a T-shirt of that size, you will give him one of them. Otherwise, you don\u0027t give him a T-shirt. You will ask the engineers in order starting from engineer \u003cspan class\u003d\"tex-span\"\u003e1\u003c/span\u003e, then engineer \u003cspan class\u003d\"tex-span\"\u003e2\u003c/span\u003e, and so on until engineer \u003cspan class\u003d\"tex-span\"\u003e\u003ci\u003en\u003c/i\u003e\u003c/span\u003e.\u003c/p\u003e"}},{"title":"Input","value":{"format":"HTML","content":"\u003cp\u003eThe first line contains two space-separated integers \u003cspan class\u003d\"tex-span\"\u003e\u003ci\u003en\u003c/i\u003e\u003c/span\u003e and \u003cspan class\u003d\"tex-span\"\u003e\u003ci\u003em\u003c/i\u003e\u003c/span\u003e \u003cspan class\u003d\"tex-span\"\u003e(1 ≤ \u003ci\u003en\u003c/i\u003e ≤ 3000, 1 ≤ \u003ci\u003em\u003c/i\u003e ≤ 300)\u003c/span\u003e, denoting the number of engineers and the number of T-shirt sizes, respectively.\u003c/p\u003e\u003cp\u003eThen \u003cspan class\u003d\"tex-span\"\u003e\u003ci\u003en\u003c/i\u003e\u003c/span\u003e lines follow, each line contains \u003cspan class\u003d\"tex-span\"\u003e\u003ci\u003em\u003c/i\u003e\u003c/span\u003e space-separated integers. The \u003cspan class\u003d\"tex-span\"\u003e\u003ci\u003ej\u003c/i\u003e\u003c/span\u003e-th integer in the \u003cspan class\u003d\"tex-span\"\u003e\u003ci\u003ei\u003c/i\u003e\u003c/span\u003e-th line represents the probability that the \u003cspan class\u003d\"tex-span\"\u003e\u003ci\u003ei\u003c/i\u003e\u003c/span\u003e-th engineer fits in a T-shirt of size \u003cspan class\u003d\"tex-span\"\u003e\u003ci\u003ej\u003c/i\u003e\u003c/span\u003e. Each probability will be given as an integer between \u003cspan class\u003d\"tex-span\"\u003e0\u003c/span\u003e and \u003cspan class\u003d\"tex-span\"\u003e1000\u003c/span\u003e, inclusive. The actual probability should be calculated as the given number divided by \u003cspan class\u003d\"tex-span\"\u003e1000\u003c/span\u003e. \u003c/p\u003e\u003cp\u003eIt is guaranteed that for any engineer, the sum of the probabilities for all \u003cspan class\u003d\"tex-span\"\u003e\u003ci\u003em\u003c/i\u003e\u003c/span\u003e T-shirts is equal to one.\u003c/p\u003e"}},{"title":"Output","value":{"format":"HTML","content":"\u003cp\u003ePrint a single real number denoting the maximum possible expected number of engineers that will receive a T-shirt.\u003c/p\u003e\u003cp\u003eFor the answer the absolute or relative error of \u003cspan class\u003d\"tex-span\"\u003e10\u003csup class\u003d\"upper-index\"\u003e - 9\u003c/sup\u003e\u003c/span\u003e is acceptable.\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\u003e2 2\n500 500\n500 500\n\u003c/pre\u003e\u003c/td\u003e\n \u003ctd\u003e\u003cpre\u003e1.500000000000\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 3\n1000 0 0\n1000 0 0\n0 1000 0\n\u003c/pre\u003e\u003c/td\u003e\n \u003ctd\u003e\u003cpre\u003e3.000000000000\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\u003e1 4\n100 200 300 400\n\u003c/pre\u003e\u003c/td\u003e\n \u003ctd\u003e\u003cpre\u003e0.400000000000\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\u003eFor the first example, bring one T-shirt of each size. With \u003cspan class\u003d\"tex-span\"\u003e0.5\u003c/span\u003e chance, either both engineers fit inside T-shirts of size \u003cspan class\u003d\"tex-span\"\u003e1\u003c/span\u003e or both fit inside T-shirts of size \u003cspan class\u003d\"tex-span\"\u003e2\u003c/span\u003e. With the other \u003cspan class\u003d\"tex-span\"\u003e0.5\u003c/span\u003e chance, one engineer fits inside a T-shirt of size \u003cspan class\u003d\"tex-span\"\u003e1\u003c/span\u003e and the other inside a T-shirt of size \u003cspan class\u003d\"tex-span\"\u003e2\u003c/span\u003e. If the first is true, the number of engineers that receive a T-shirt is one. If the second is true, the number of such engineers is two. Hence, the expected number of engineers who receive a T-shirt is \u003cspan class\u003d\"tex-span\"\u003e1.5\u003c/span\u003e. This is maximum possible expected number of engineers for all sets of T-shirts. \u003c/p\u003e\u003cp\u003eFor the second example, bring two T-shirts of size \u003cspan class\u003d\"tex-span\"\u003e1\u003c/span\u003e and one T-shirt of size \u003cspan class\u003d\"tex-span\"\u003e2\u003c/span\u003e. This way, each engineer will definitely receive a T-shirt of his size.\u003c/p\u003e\u003cp\u003eFor the third example, bring one T-shirt of size \u003cspan class\u003d\"tex-span\"\u003e4\u003c/span\u003e.\u003c/p\u003e"}}]}