A certain big IT company which we will not name in order not to get
sued, are preparing to launch a new version of their flagship product.
Having just been employed as a developer on the project, you have been
given a list of open bugs that should be fixed in the new version.
Being bugs, you are not exactly certain how to fix them, even though
you have some ideas. For each bug you are able to estimate your
ability to quickly fix the bug. Of course, these estimates may be
wrong, so if you try to fix a bug and fail, you will revise the
estimate of your ability to fix this bug.
To be specific, we use the following probabilistic model for the bug
fixing process: for each bug, there is an associated fix
probability p
. Every hour, you choose one bug to work on, and work
on this bug for the entire hour (if you manage to fix the bug in less
then an hour, you celebrate by having coffee and taunting your
coworkers for the remaining part of the hour). The probability that
you succeed in fixing the bug during this hour is p
. If you fail to
resolve the bug, the fix probability for this bug is reduced to p . f
,
where f1
is a factor indicating how much faith you lose
in your ability after a failure. The fix probabilities for the other
bugs remain unchanged. The next hour, you again choose an open bug to
work on, and so on. This is repeated until the new version is
released, and you are allowed to go home and sleep.
In addition, each bug has a severity s
indicating how severe
the bug is (or alternatively, the value of fixing the bug). Clearly,
it is possible that you will not manage to fix all the bugs before
the product is released. In order to make as good an impression on
your boss as possible, you would like to maximize the total severity
of those bugs which you do manage to resolve, by carefully choosing
which bugs to work on. What will be the expected value of the total
severity of fixed bugs, provided that you, every hour, choose which
bug to work on in such a way that this quantity is maximized?
The input file contains several test cases, each of them as described below.
The first line of input contains three numbers B
, T
and f
, where
0B10
is an integer giving the number of open bugs,
0T100
is an integer giving the number of hours left until the new
version is released, and
0f1
is a real number as described
above.
Each of the following B
lines describe an open bug. Each such
description contains two numbers p
and s
, where
0p1
is
a real number giving the initial fix probability of the bug and
0s10 000
is an integer giving the severity of the bug.
For each test case, write to the output a line containing the expected total severity of bugs fixed,
provided you work in a way which maximizes this quantity. Any answer
with either absolute or relative error smaller than 10-6
is
acceptable.
1 2 0.950000
0.700000 50
2 2 0.500000
0.750000 100
0.750000 20
44.975
95.6250000000000000000