#include <iostream> #include <cstdio> #include <cstring> #include <cmath> #define N 2000005 #define p(a,b) (a-1)*m+b #define q(a,b) p(a,b)+n*m using namespace std; const int inf=(1 << 26); int n,m,S,T,d; int idx,head[N],cur[N],q[N]; int e[N],ne[N],w[N]; int ans; char mp[110][220]; int g[220][220]; int sum,ap[220][220]; inline void add(int u,int v,int f) { e[idx]=v; w[idx]=f; ne[idx]=head[u]; head[u]=idx++; } inline bool bfs() { int f=0,t=0; memset(cur,-1,sizeof(cur)); q[t++]=0; cur[S]=0; while(f<t) { int now=q[f++]; for(int i=head[now]; ~i; i=ne[i]) { int v=e[i]; if(cur[v]==-1&&w[i]) { cur[v]=cur[now]+1; q[t++]=v; } } } if(cur[T]!=-1) return 1; return 0; } inline int dfs(int x,int f) { if(x==T) return f; int w1,used=0; for(int i=head[x]; ~i; i=ne[i]) { int v=e[i]; if(cur[v]==cur[x]+1&&w[i]) { w1=dfs(v,min(f-used,w[i])); w[i]-=w1; w[i^1]+=w1; used+=w1; if(used==f) return f; } } if(!used) cur[x]=-1; return used; } void dinic() { while(bfs()) ans+=dfs(0,0x3f3f3f3f); } bool dis(int a,int b,int x,int y) { return (a-x)*(a-x)+(b-y)*(b-y)<=d*d; } bool check(int x,int y) { if(n-x<d||m-y<d||x<=d||y<=d) return true; return false; } int main() { memset(head,-1,sizeof head); cin>>n>>m>>d; S=0,T=n*m*2+1; for(int i=1; i<=n; i++) cin>>mp[i]+1; for(int i=1; i<=n; i++) for(int j=1; j<=m; j++) ap[i][j]=mp[i][j]-'0'; for(int i=1; i<=n; i++) cin>>mp[i]+1; for(int i=1; i<=n; i++) for(int j=1; j<=m; j++) { if(mp[i][j]=='L') { add(S,p(i,j),1); add(p(i,j),S,0); sum++; } if(check(i,j)) { add(q(i,j),T,inf); add(T,q(i,j),0); } if(ap[i][j]) { add(p(i,j),q(i,j),ap[i][j]); add(q(i,j),p(i,j),0); } for(int x=1; x<=n; x++) for(int y=1; y<=m; y++) { if(x==i&&y==j)continue; if(dis(i,j,x,y)) add(q(i,j),p(x,y),inf),add(p(x,y),q(i,j),0); } } dinic(); cout<<sum-ans<<endl; return 0; }