Dice and Ladders

The ladder game is a fun children's game. The rules are as follows. You start at cell number 1 and each round you roll a die and move the number of cells shown on the die. If you end on a cell where a ladder starts, you follow that ladder in its direction a single time. That is, if the ladder ends at a cell where a new ladder starts, you do not follow the new ladder. The game ends when you move to or past the last cell.

Your task is to find the minimum number of die rolls required to finish the game with a probability of at least p.

The first line contains three integers r (3 ≤ r ≤ 8), c (3 ≤ c ≤ 8), and k (0 ≤ k ≤ 50), the number of rows, the number of columns, and the number of ladders, respectively. The second line contains a single floating-point number p (0 < p < 1) as described above, given with at most 6 digits after the decimal point.

Then follow k lines, each describing a ladder. The i-th of these lines contains two integers si (2 ≤ si < r · c) and ei (1 ≤ ei ≤ r · c), the starting cell and the ending cell of ladder i, respectively. Two ladders never start at the same cell, but multiple ladders may end at the same cell. The cells are numbered as in the illustration: cell 1 is in the bottom left corner and there are c more cells in the same row. Cell c + 1 starts at the left of the second row, and so on.

It is guaranteed that it is possible to finish the game with probability p in fewer than 108 die rolls. The input is also constructed so that the expected number of die rolls needed to finish the game with probability p equals the expected number of die rolls needed to finish the game with probability p ± 10−9.

Output a single integer, the minimum number of die rolls required to finish the game with probability at least p.