Fixing the Bugs

Interview

Time limit1sMemory limit128 MB

Summary

With B bugs, T hours, and a failure factor f, choose each hour's bug by dynamic programming to maximize the expected total severity fixed.

Level: Medium7 of 10
Topics: Dynamic programming, Probability
Solved: No attempts yet

Problem

A large software company is preparing to launch a new version of its flagship product. As a newly hired developer on the project, you are given a list of open bugs to fix before the new version ships.

Because they are bugs, you are not certain how to fix them, though you have some ideas. For each bug you can estimate how likely you are to fix it quickly. These estimates may be wrong, so if you attempt a bug and fail, you revise your estimate for that bug downward.

We use the following probabilistic model. Each bug has a current fix probability $p$ . Every hour you choose one open bug and work on it for the whole hour (if you fix it in less than an hour, you spend the rest of the hour celebrating). You fix the bug during that hour with probability $p$ . If you fail, that bug's fix probability is multiplied by a factor $f$ (with $0 \le f \le 1$ ), becoming $p \cdot f$ ; the fix probabilities of the other bugs are unchanged. The next hour you again choose an open bug, and so on, until the new version is released.

Each bug also has a severity $s$ , indicating how valuable fixing it is. You may not manage to fix every bug before release, so to make the best impression on your boss you want to maximize the total severity of the bugs you do fix, by carefully choosing which bug to work on each hour. If every hour you choose the bug to work on so as to maximize this quantity, what is the expected total severity of the bugs you fix?

Input

The first line contains three numbers $B$ , $T$ , and $f$ :

an integer $B$ ( $0 \le B \le 10$ ), the number of open bugs,
an integer $T$ ( $0 \le T \le 100$ ), the number of hours left until release,
a real number $f$ ( $0 \le f \le 1$ ), the confidence factor described above.

Each of the next $B$ lines describes one open bug with two numbers $p$ and $s$ : a real number $p$ ( $0 \le p \le 1$ ), the bug's initial fix probability, and an integer $s$ ( $0 \le s \le 10000$ ), its severity.

Output

Print the maximum expected total severity of the bugs you fix, assuming you work so as to maximize it, rounded to exactly six digits after the decimal point.

Examples4

Example 1
Input
```
1 2 0.950000
0.700000 50
```
Expected output
```
44.975000
```

Example 2

Input

2 2 0.500000
0.750000 100
0.750000 20

Expected output

95.625000

Example 3
Input
```
1 3 1.000000
0.500000 100
```
Expected output
```
87.500000
```
Example 4
Input
```
1 1 0.500000
1.000000 100
```
Expected output
```
100.000000
```