주사위와 사다리

사다리 게임은 재미있는 어린이 게임으로, 규칙은 다음과 같다. 1번 칸에서 시작하여 매 라운드마다 주사위를 굴려 나온 수만큼 이동한다. 이동한 칸에서 사다리가 시작된다면 그 사다리를 한 번만 따라 이동한다. 즉, 사다리가 끝나는 칸에서 새로운 사다리가 시작되더라도 그 새로운 사다리는 타지 않는다. 마지막 칸으로 이동하거나 마지막 칸을 지나치면 게임이 끝난다.

확률이 적어도 p 이상이 되도록 게임을 끝내기 위해 필요한 최소 주사위 굴림 횟수를 구하는 것이 목표이다.

첫째 줄에 행의 수 r (3 ≤ r ≤ 8), 열의 수 c (3 ≤ c ≤ 8), 사다리의 수 k (0 ≤ k ≤ 50)가 주어진다. 둘째 줄에 위에서 설명한 확률 p (0 < p < 1)가 주어지며, 소수점 이하 최대 6자리까지 주어진다.

이어서 k개의 줄에 각각 사다리를 나타내는 두 정수 si (2 ≤ si < r · c)와 ei (1 ≤ ei ≤ r · c)가 주어진다. si는 사다리 i의 시작 칸, ei는 끝나는 칸이다. 두 사다리가 같은 칸에서 시작하는 경우는 없지만, 여러 사다리가 같은 칸에서 끝날 수는 있다. 칸은 그림과 같이 번호가 매겨지며, 1번 칸은 왼쪽 아래 모서리에 있고 같은 행에 c개의 칸이 더 있다. c + 1번 칸은 둘째 행의 왼쪽에서 시작하며, 이와 같은 방식으로 번호가 매겨진다.

확률 p 이상으로 게임을 끝낼 수 있는 주사위 굴림 횟수가 108번 미만임이 보장된다. 또한 입력은 확률 p로 게임을 끝내기 위한 주사위 굴림 횟수의 기댓값과 확률 p ± 10−9로 게임을 끝내기 위한 주사위 굴림 횟수의 기댓값이 같도록 구성된다.

확률이 적어도 p 이상이 되도록 게임을 끝내기 위해 필요한 최소 주사위 굴림 횟수를 나타내는 정수 하나를 출력한다.