Entangled with Lottery

時間制限 : 2 sec, メモリ制限 : 65536 KB

E: Entangled with Lottery

ICPC で良い成績を収めるには修行が欠かせない.うさぎは ICPC で勝ちたいので,今日も修行をすることにした.

今日の修行は,あみだくじを利用して,未来を読む力をつけて運気を高めようというものである.もちろん直感に頼るだけでなく,綿密な確率計算も欠かせない.

今回考えるあみだくじは,長さ H + 1 センチメートルの縦棒 N 本からなる.うさぎは棒の上部を見て,N 本のうち 1 本を選ぶことになる.棒の下部には,左から P 本目の棒の場所にのみ「当たり」と書かれている.あみだくじにはいくつかの横棒が含まれる.横棒の配置に関して,以下の条件を考えよう.

  • 各横棒は,a を 1 以上 H 以下の整数として,縦棒の上端から a センチメートルの高さにある.
  • 各横棒は,隣り合った 2 本の縦棒のみを結ぶ.
  • 同じ高さには複数の横棒は存在しない.

うさぎはこれらの条件を満たすように M 本の横棒を引いた.あいにくうさぎは記憶力が良いので,当たりの位置や横棒の位置をすべて覚えてしまっており,あみだくじを楽しめない.そこで友達のねこにさらに横棒を追加してもらうことにした.

まず,うさぎは当たりを狙って N 本の棒のうち 1 本を選ぶ.その後,ねこは以下の操作をちょうど K 回行う.

  • 横棒を追加しても上で指定された条件を満たすような場所のうち 1 箇所を無作為に選ぶ.ここで,どの場所も等確率で選ばれるものとする.選んだ場所に横棒を追加する.

そして,うさぎが選んだ棒が当たりであったかを判定する.棒の辿り方は通常のあみだくじと同様である (横棒に出会うたびに隣の縦棒に移る).うさぎは,可能な限り当たりとなる確率を高くしたい.

Input

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

Ai, Bi (1 ≤ iM) はうさぎが引いた横棒のうち i 番目のものが,縦棒の上端から Ai センチメートルの高さにあり,左から Bi 本目の縦棒と左から Bi + 1 本目の縦棒を結ぶことを表す整数である.

2 ≤ H ≤ 500,2 ≤ N ≤ 100,1 ≤ PN,1 ≤ M ≤ 100,1 ≤ K ≤ 100,M + KH,1 ≤ A1 < A2 < ... < AMH,1 ≤ BiN - 1 を満たす.

Output

当たりとなる確率が最大となるようにうさぎが棒を選んだときの,当たりとなる確率を 1 行に出力せよ.10-6 以下の絶対誤差が許容される.

Sample Input 1

9 4 3 2 1
2 1
7 3

Sample Output 1

0.571428571

Sample Input 2

9 4 3 2 3
2 1
7 3

Sample Output 2

0.375661376

Source: ACM-ICPC Japan Alumni Group Summer Camp 2011 , Day 2, Tokyo, Japan, 2011-09-18
http://acm-icpc.aitea.net/