22498번 - Entangled with Lottery 스페셜 저지다국어

문제

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

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

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

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

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

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

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

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

입력

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

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

2 ≤ H ≤ 500,2 ≤ N ≤ 100,1 ≤ P ≤ N,1 ≤ M ≤ 100,1 ≤ K ≤ 100,M + K ≤ H,1 ≤ A₁ < A₂ < ... < A_M ≤ H,1 ≤ B_i ≤ N - 1 を満たす.

출력

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

제한

힌트