Welcome to ZOJ
 Contests Information Problems Runs Statistics Ranklist Clarification
115 - The 12th Zhejiang University Programming Contest - G
Hit the Target!

Time Limit: 6 Seconds      Memory Limit: 65536 KB

Alice and Bob are playing a game on shooting. In this game, there are N guns and M targets. Each gun has only one bullet and can shoot at only one target. What's more, they are located in different places so that they can hit different targets. In this game, the guns appear one by one and disappear before the next gun appears, and so will the targets. From the N guns, Alice will choose P consecutive guns in equivalent possibility. Then Bob can choose Q consecutive targets so that he can shoot as many hits as possible. Now you are asked to calculate the expected hits Bob can get.

#### Input

There are multiple test cases. The first line of input contains an integer T (0 < T ≤ 50), indicating the number of test cases. Then T test cases follow.

The first line of each test case contains 4 integers N, M, P and Q (0 < PN ≤ 50000, 0< QM ≤ 50000), indicating the number of guns, the number of targets, the number of consecutive guns Bob can use and the number of consecutive targets Bob can shoot. The next line contains one integer K (0 ≤ K ≤ 100000). Each of the K lines contains two integers Gi and Ti (1 ≤ GiN, 1 ≤ TiM), indicating the Gi-th gun can hit the Ti target. No duplicated (Gi, Ti) occurs.

#### Output

For each test case, output the expected number of hits in one line, accurate to 0.01.

```5
2 1 2 1
2
1 1
2 1
3 2 2 2
2
1 1
3 2
2 2 1 1
2
1 1
2 2
4 5 2 3
4
1 1
2 2
3 5
4 3
4 7 3 2
7
1 1
1 5
2 4
2 7
3 1
3 6
4 7
```

```2.00
1.00
1.00
1.67
2.50
```

#### Hint

In the first sample, the only choice is to choose all of the guns and targets. And the two guns can hit the target. So the number of hits is 2.
In the second sample, Alice can only choose both gun, but Bob cannot choose the first target and the third target simultaneously. So he can only get 1 hit.
In the third sample, after Alice choose one of the gun, Bob can choose the corresponding target so that he can always get one hit no matter how Alice choose the gun.
In the fourth sample, Bob can get 2, 1, 2 hits correspondingly when Alice choose different guns.

Author: GUAN, Yao
Submit    Status