extern crate core;

use std::fmt;
use std::cmp::{max, min};
macro_rules! read_line{
    () => {{
        let mut line = String::new();
        std::io::stdin().read_line(&mut line).ok();
        line
    }};
    (delimiter: ' ') => {
        read_line!().split_whitespace().map(|x|x.to_string()).collect::<Vec<_>>()
    };
    (delimiter: $p:expr) => {
        read_line!().split($p).map(|x|x.to_string()).collect::<Vec<_>>()
    };
    (' ') => {
        read_line!(delimiter: ' ')
    };
    ($delimiter:expr) => {
        read_line!(delimiter: $delimiter)
    };
    (' '; $ty:ty) => {
        read_line!().split_whitespace().map(|x|x.parse::<$ty>().ok().unwrap()).collect::<Vec<$ty>>()
    };
    ($delimiter:expr; $ty:ty) => {
        read_line!($delimiter).into_iter().map(|x|x.parse::<$ty>().ok().unwrap()).collect::<Vec<$ty>>()
    };
}
macro_rules! let_all {
    ($($n:ident:$t:ty),*) => {
        let line = read_line!(delimiter: ' ');
        let mut iter = line.iter();
        $(let $n:$t = iter.next().unwrap().parse().ok().unwrap();)*
    };
}
fn solve(memo:&mut Vec<Vec<Vec<f64>>>, p: usize, n: usize, current: usize, h: usize, k: usize, free: usize, borders: &Vec<usize>) -> f64 {
    if k > free {
        0_f64
    }else if h == memo.len() {
        if p == current {
            1_f64
        }else {
            0_f64
        }
    }else if memo[h][current][k] < 0_f64 {
        let r = match borders[h] {
            b if b == current => {
                solve(memo, p, n, current + 1, h + 1, k, free, borders)
            }
            b if b + 1 == current => {
                solve(memo, p, n, current - 1, h + 1, k, free,borders)
            }
            b if b == n => {
                if k == 0 {
                    solve(memo, p, n, current, h + 1, k, free - 1, borders)
                }else {
                    let choice = (k as f64) / free as f64;
                    let prob = 1_f64 / (n - 1) as f64;
                    if current == 0 {
                        choice * ((1_f64 - prob) * solve(memo, p, n, current, h + 1, k - 1, free - 1, borders) + prob * solve(memo, p, n, current + 1, h + 1, k - 1, free - 1, borders)) +
                            (1_f64 - choice) * solve(memo, p, n, current, h + 1, k, free - 1, borders)
                    }else if current == n - 1 {
                        choice * ((1_f64 - prob) * solve(memo, p, n, current, h + 1, k - 1, free - 1, borders) + prob * solve(memo, p, n, current - 1, h + 1, k - 1, free - 1, borders)) +
                            (1_f64 - choice) * solve(memo, p, n, current, h + 1, k, free - 1, borders)
                    }else {
                        choice * ((1_f64 - prob * 2_f64) * solve(memo, p, n, current, h + 1, k - 1, free - 1, borders) + prob * (solve(memo, p, n, current - 1, h + 1, k - 1, free - 1, borders) + solve(memo, p, n, current + 1, h + 1, k - 1, free - 1, borders))) +
                            (1_f64 - choice) * solve(memo, p, n, current, h + 1, k, free - 1, borders)
                    }
                }
            }
            _ => solve(memo, p, n, current, h + 1, k, free,borders)
        };
        memo[h][current][k] = r;
        r
    }else {
        memo[h][current][k]
    }
}
fn main() {
    let_all!(h: usize, n: usize, p: usize, m: usize, k: usize);
    let mut borders: Vec<usize> = vec![n; h];
    for _ in 0 .. m {
        let_all!(a: usize, b: usize);
        borders[a - 1] = b - 1;
    }
    let borders = borders;
    let mut memo = vec![vec![vec![-1_f64; k + 1]; n]; h];
    let mut max = 0_f64;
    for i in 0 .. n {
        let r = solve(&mut memo, p - 1, n, i, 0, k, h - m, &borders);
        if r > max {
            max = r;
        }
    }
    println!("{:.*}", 15, max);
}



Measured memory_bytes: 50180