You have won the labour lottery and are now an apartment manager at 100 KRUSHVICE st. There, your job is to ensure that the tenants are satisfied, and more important, following the government directives.
In order to do the latter, you plan to install cameras in tenant 's room. Camera in the -th person's room has a probability of of discovering that person doing something illegal. (Note that discovering a person twice has no additional effect). However, due to budget cuts, your number of cameras is limited to . Determine the maximum expected number of people caught doing something illegal if you only install up to cameras, for ALL values of from to .
The probability is a real number between 0 and 1.
Line : An integer, , the number of tenants.
Next Lines: An integer , the number of cameras planned to be installed in the th person room, and real numbers, the values of .
lines, each with a single real number, the maximum expected value after installing cameras. Your answer will be accepted if it differs from the expected answer by up to .
3 3 0.5 0.5 0.5 2 0.4 0.25 1 0.3
0.50000000 0.90000000 1.20000000 1.45000000 1.60000000 1.72500000
Also note that
0.50000000 0.90000000 1.20000000 1.44999999 1.60000000 1.72500001
is also a valid output, for example