복권과 얽히다

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 ≤ A1 < A2 < ... < A**M ≤ H, 1 ≤ B**i ≤ N - 1을 만족한다.

당첨이 될 확률이 최대가 되도록 토끼가 막대를 골랐을 때의 당첨 확률을 1행에 출력하라. 10-6 이하의 절대 오차가 허용된다.