Problem: Training is indispensable for achieving good results at ICPC. Rabbit wants to win at ICPC, so he decided to practice today as well.

Today's training is to use the Amidakuji to improve luck by gaining the ability to read the future. Of course, not only relying on intuition, but also detailed probability calculation is indispensable.

The Amidakuji we consider this time consists of N vertical bars with a length of H + 1 cm. The rabbit looks at the top of the stick and chooses one of the N. At the bottom of the bar, "hit" is written only at the location of the Pth bar from the left. The Amidakuji contains several horizontal bars. Consider the following conditions regarding the arrangement of horizontal bars.

* Each horizontal bar is at a height of a centimeter from the top of the vertical bar, where a is an integer greater than or equal to 1 and less than or equal to H.
* Each horizontal bar connects only two adjacent vertical bars.
* There are no multiple horizontal bars at the same height.



The rabbit drew M horizontal bars to satisfy these conditions. Unfortunately, the rabbit has a good memory, so I remember all the hit positions and the positions of the horizontal bars, so I can't enjoy the Amidakuji. So I decided to have my friend's cat add more horizontal bars.

First, the rabbit chooses one of the N sticks, aiming for a hit. After that, the cat performs the following operations exactly K times.

* Randomly select one of the locations that meet the conditions specified above even if a horizontal bar is added. Here, it is assumed that every place is selected with equal probability. Add a horizontal bar at the selected location.



Then, it is determined whether the stick selected by the rabbit was a hit. The way to follow the bars is the same as the normal Amidakuji (every time you meet a horizontal bar, you move to the next vertical bar). Rabbits want to have a high probability of winning as much as possible.



Input


H N P M K
A1 B1
...
AM BM


In Ai, Bi (1 ≤ i ≤ M), the i-th horizontal bar drawn by the rabbit is at a height of Ai centimeters from the top of the vertical bar, and the second vertical bar from the left and Bi from the left. + An integer that represents connecting the first vertical bar.

2 ≤ H ≤ 500, 2 ≤ N ≤ 100, 1 ≤ P ≤ N, 1 ≤ M ≤ 100, 1 ≤ K ≤ 100, M + K ≤ H, 1 ≤ A1 <A2 <... <AM ≤ H, Satisfy 1 ≤ Bi ≤ N-1.

Output

Output the probability of winning in one line when the rabbit chooses a stick so that the probability of winning is maximized. Absolute errors of 10-6 or less are allowed.

Examples

Input

9 4 3 2 1
2 1
7 3


Output

0.571428571


Input

9 4 3 2 3
2 1
7 3


Output

0.375661376

Solution (in CPP):

Solution:
#include <stdio.h>
#include <cmath>
#include <algorithm>
#include <cfloat>
#include <stack>
#include <queue>
#include <vector>
#include <string>
#include <iostream>
#include <set>
#include <map>
#include <time.h>
typedef long long int ll;
typedef unsigned long long int ull;
#define BIG_NUM 2000000000
#define MOD 1000000007
#define EPS 0.000000001
using namespace std;


#define NUM 503

double dp[2][102][102];
bool is_exist[NUM];
int line_loc[NUM],can_write_num[NUM];

int main(){

	int H,N,P,M,K;
	scanf("%d %d %d %d %d",&H,&N,&P,&M,&K);

	for(int i = 0; i <= H+1; i++){
		is_exist[i] = false;
		can_write_num[i] = 1;//その高さ以下で、横棒を引ける高さの数
	}

	int height,loc;
	for(int loop = 0; loop < M; loop++){
		scanf("%d %d",&height,&loc);
		is_exist[height] = true;
		line_loc[height] = loc;
		can_write_num[height] = 0;
	}

	for(int h = 2; h <= H+1; h++)can_write_num[h] += can_write_num[h-1];

	for(int i = 0; i < 2; i++){
		for(int k = 0; k <= K; k++){
			for(int pos = 1; pos <= N; pos++)dp[i][k][pos] = 0; //dp[高さ][横棒の設置本数][位置] = ゴール確率
		}
	}

	int CURRENT = 0,NEXT = 1;

	dp[CURRENT][0][P] = 1.0;

	double loc_possi = 1.0/(double)(N-1),height_possi;

	for(int h = H; h >= 1; h--){
		if(is_exist[h]){ //既に横棒が引かれている場合:該当する2箇所の確率を交換する

			for(int num = 0; num <= K; num++){
				swap(dp[CURRENT][num][line_loc[h]],dp[CURRENT][num][line_loc[h]+1]);
			}

		}else{ //横棒が引かれていない場合

			for(int num = 0; num <= K; num++){
				for(int pos = 1; pos <= N; pos++)dp[NEXT][num][pos] = 0.0;
			}

			for(int num = 0; num <= K; num++){

				height_possi = (double)(K-num)/(double)can_write_num[h]; //その高さが選ばれる確率

				for(int pos = 1; pos <= N; pos++){

					//右に動く(★交換回数が1増える!!★)
					if(pos != N){
						dp[NEXT][num+1][pos+1] += height_possi*loc_possi*dp[CURRENT][num][pos];
					}

					//左に動く(★交換回数が1増える!!★)
					if(pos != 1){
						dp[NEXT][num+1][pos-1] += height_possi*loc_possi*dp[CURRENT][num][pos];
					}

					//★変わらず★
					//自分の高さが選ばれない場合
					dp[NEXT][num][pos] += (1-height_possi)*dp[CURRENT][num][pos];

					//自分の高さが選ばれ、かつ自分以外の場所が選ばれる場合
					if(pos != 1 && pos != N){
						dp[NEXT][num+1][pos] += height_possi*(1.0-loc_possi*2)*dp[CURRENT][num][pos];
					}else{ //pos == 1 || pos == N
						dp[NEXT][num+1][pos] += height_possi*(1.0-loc_possi)*dp[CURRENT][num][pos];
					}
				}
			}
			swap(CURRENT,NEXT);
		}
	}

	double ans = 0.0;
	for(int pos = 1; pos <= N; pos++)ans = max(ans,dp[CURRENT][K][pos]);

	printf("%.10lf\n",ans);

	return 0;
}