레이저 증폭

Sophie는 레이저 공장에서 일한다. 이 공장은 새 레이저 증폭기를 도입하려 한다. 이 장치는 격자이며, 격자의 각 노드는 광자를 받아 다시 방출한다. 왼쪽이나 아래쪽에서 받은 광자 하나마다 위쪽으로 하나, 오른쪽으로 하나의 광자를 방출하고, 이 광자들은 해당 방향에 있는 노드가 받는다. 그 방향에 노드가 없으면 광자는 사라진다. 아쉽게도 산업 규모 생산은 완벽하지 않아 격자의 일부 노드는 고장 나 있다. 고장 난 노드는 광자를 받지도, 방출하지도 않는다. 더 정확히 말하면, 일부 노드는 확실히 고장 나 있고 나머지 각 노드는 확률 $1-p$로 고장 나 있다. 다행히 생산 중 압력을 조절하면 $p$의 값을 바꿀 수 있다. Sophie의 임무는 격자의 왼쪽 아래 노드로 광자 하나를 보냈을 때 기대값으로 $k$개의 광자가 격자의 오른쪽 위 모서리에 도달하도록 하는 $p$의 값을 계산하거나, 그것이 불가능함을 밝히는 것이다. 그녀를 도와주자.

참고: 오른쪽 위 모서리의 노드가 고장 났다면 그 노드는 광자를 받지 않는다.

입력의 첫째 줄에는 네 양의 정수 $w$, $h$, $n$, $k$가 주어진다. ($1 \le w, h \le 5\,000$, $0 \le n \le 50$, $1 \le k \le 10^{10000}$) 이는 각각 격자의 크기(너비와 높이), 고장 난 노드의 수, 노드 $(w-1,h-1)$에서 받아야 하는 광자의 수를 나타낸다. 다음 $n$개 줄에는 고장 난 노드의 정보가 한 줄에 하나씩 주어진다. 각 줄에는 두 양의 정수 $x, y$가 주어진다. ($0 \le x < w$, $0 \le y < h$) 이는 고장 난 노드의 좌표이다. 이 노드들은 모두 서로 다르다.

실수 하나를 출력한다. 이는 구하는 확률 $p$이다. 그러한 확률이 존재하고 절대 오차 또는 상대 오차가 $10^{-6}$ 이하이면 정답으로 인정된다. 그러한 확률이 존재하지 않으면 $-1$을 출력한다. 그러한 확률이 실제로 존재하지 않으면 $-1$이 정답으로 인정된다.

예제 1에서 상황은 아래 그림과 같다. 광자는 Start로 표시된 격자 노드에서 시작하고, 광자 센서는 Finish로 표시된 격자 노드에 있다.

예제 2에서는 $p = 1$이어도 $4$개의 광자만이 오른쪽 위 모서리에 도달한다.