[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 C_i cookies with probability P_i 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.

For example, let's assume there are N = 3 counting machines, which we will call m₁, m₂ and m₃, having each of them the possibility to select C₁ = 1 or C₂ = 2 cookies with probability P₁ = P₂ = ½. If we want to produce M = 2 packages with G = 5 cookies per package, a possible turn of events is the following. Before starting, the three machines select C₂ = 2 cookies each (this will happen with probability ½ * ½ * ½ = ⅛). In the first iteration, the software can then choose among the subsets {m₁, m₂, m₃}, {m₁, m₂}, {m₁, m₃} and {m₂, m₃}, each with probability ¼ because they all have a difference of one cookie with the desired number G = 5. Supposing that the subset S = {m₂, m₃} is chosen, then the four cookies selected by machines m₂ and m₃ will be packed together. These machines will then be activated again, resulting for example in m₂ selecting C₁ = 1 cookie and m₃ selecting C₂ = 2 cookies (which will occur with probability ½ * ½ = ¼). At this point the first iteration ends, the counting machines m₁, m₂ and m₃ having selected 2, 1 and 2 cookies respectively. In the second iteration, the software must necessarily choose the subset S = {m₁, m₂, m₃} as it contains exactly five cookies, which will therefore be packed together. Finally, the three counting machines will be activated once more and the process will end, having produced the M = 2 desired packages. Note that the net probability for the process here described is ⅛ * ¼ * ¼ = 1/128, and that the average number of cookies per package is in this case 4.5 (because two packages were produced, one of them having four and the other five cookies).

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 ≤ 10⁷). Each of the following K lines contains an integer C_i and a rational P_i, indicating that the counting machines will select C_i cookies with probability P_i (1 ≤ C_i ≤ 100 and 0 < P_i ≤ 1 for i = 1, 2, ..., K, being P_i given with exactly two digits after the decimal marker). Note that C_i ≠ C_j for i ≠ j and that ∑ P_i = 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