## TAP2015E - Perfect packing

no tags

[Due to SPOJ restrictions, this problem has been modified with respect to the original version used in the Argentinian Programming Tournament of 2015 in order to have multiple test cases per input file. The original version of this problem (in Spanish) can be found at http://torneoprogramacion.com.ar/wp-content/uploads/2015/09/pruebaTAP2015.pdf ]

One of the most difficult stages to automate in an industrial cookie production line is the one corresponding to packing. The goal is to design an apparatus capable of counting a precise number G of cookies to be put in a package, and the challenge resides in the fact that the cookies may have markedly different shapes, e.g. of various animals.

In the cookie factory where you work the design team has been unable to overcome these difficulties. The best design they have achieved corresponds to a counting machine which, when activated, can select Ci cookies with probability Pi for i = 1, 2, ..., K. Having already spent the entire budget allocated to this task, you will have to find a way to make something useful out of this.

Fortunately, you have come up with the following idea to save the project. You shall build an automated packager using N counting machines such as the one described above, along with a special regulating software that will perform the following process iteratively. Before starting the first iteration the N counting machines are activated, each one selecting certain number of cookies. In each iteration, the software will choose a non-empty subset S of the N machines such that the sum of the selected cookies is as close as possible to the desired value G (in the sense that the absolute value of the difference between this number and G is minimum). If there is more than one subset satisfying this condition, the software will choose as S any of them with uniform probability. The cookies selected by the counting machines in S will then be removed and packed together. Finally, each of the machines in S will be activated again in order for it to select certain number of cookies, while the counting machines not in S remain unaltered (that is, with the number of cookies they selected in the previous iteration). This process will be repeated until the desired number M of packages has been obtained.

Your boss is not completely convinced that this system will work, so he requires from you some concrete proof of concept. To convince him, it will suffice to calculate the expected number of cookies per package after producing M packages consecutively, if you assume that the N counting machines always select cookies according to the given probabilities.

### Input

There are multiple test cases in the input file. For each test case, the first line contains four integers N, K, G and M. The value N represents the number of counting machines to use (1 ≤ N ≤ 4), K represents the number of possible quantities of cookies each counting machine can select (1 ≤ K ≤ 6), G represents the desired number of cookies per package (1 ≤ G ≤ 100), and M represents the total number of packages to produce (1 ≤ M ≤ 107). Each of the following K lines contains an integer Ci and a rational Pi, indicating that the counting machines will select Ci cookies with probability Pi (1 ≤ Ci ≤ 100 and 0 < Pi ≤ 1 for i = 1, 2, ..., K, being Pi given with exactly two digits after the decimal marker). Note that Ci ≠ Cfor i ≠ j and that ∑ Pi = 1.

### Output

For each test case, print one line containing a rational representing the expected number of cookies per package after having produced M packages as described in the problem statement. Print the result with exactly 6 digits after the decimal marker, rounding if necessary.

### Example

```Input:
3 2 5 1
1 0.50
2 0.50
3 2 5 2
1 0.50
2 0.50

Output:
4.312500
4.327148
```