Untitled

#include <iostream>
#include <bits/stdc++.h>
#include <cstring>
#include<numeric>
using namespace std;
long long mod = 1e9+9;
#define endl '\n'
#define ll long long
#define ull unsigned long long
const int N = 105;
char grid[N][N];
int scores[N][N];
int n,m,d;
double p;

int dx[4] = {1,-1,0,0};
int dy[4] = {0,0,1,-1};
/* up down right left */

bool valid(int i, int j) {
    if(i<0 || i>=n || j<0 || j>=m || grid[i][j]=='#') return 0;
    return 1;
}

double dfs(int x, int y, int move, double cum_p) {
    double now = cum_p*scores[x][y];
    if(grid[x][y]=='*' || move>=d) return now;

    double scores_dir[4];
    double other_p = 0.5*(1-p);

    for(int i=0;i<4;i++) {
        int next_x = x+dx[i], next_y = y+dy[i];
        if(valid(next_x,next_y)) {
            scores_dir[i]= dfs(next_x,next_y,move+1,cum_p*p);
        }
        else {
            scores_dir[i]= dfs(x,y,move+1,cum_p*p);
        }
    }
    double ans=INT_MIN;
    for(int i=0;i<4;i++) ans= max(ans,max(scores_dir[i],scores_dir[i]*other_p/p));
    return now+ans;
}

int main() {
    ios::sync_with_stdio(false); cin.tie(0); cout.tie(0);
//    freopen("test_input.txt","r",stdin);
//    freopen("test_output.txt","w",stdout);
    cin>>n>>m>>d>>p;
    int start_i,start_j;
    cin>>start_i>>start_j;
    for(int i=0;i<n;i++) for(int j=0;j<m;j++) cin>>grid[i][j];
    for(int i=0;i<n;i++) for(int j=0;j<m;j++) cin>>scores[i][j];
    cout<<fixed<<setprecision(6)<<dfs(start_i-1,start_j-1,0,1);
}