## Cameras

View as PDF

Points: 5
Time limit: 3.0s
Memory limit: 256M

Authors:
Problem types

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 .

#### Constraints

The probability is a real number between 0 and 1.

#### Input Format

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 .

#### Output Format

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 .

#### Sample Input

3
3 0.5 0.5 0.5
2 0.4 0.25
1 0.3

#### Sample Output

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.