#include <cmath>#include <ctime>#include <iostream>#include <string>#include <vector>#include <cstdlib>#include <cstdio>#include <algorithm>#include <cstring>using namespace std;long long N,M,m,n,T;int map[2010][2010];long long a,b;bool Judge(){ if(a>=b && b>=1 && b*(m+1)+m*a==M && b*(n+1)+n*a==N) return true; return false;}char str[2010][2010];int goal[2010][2010];int vis[300];int link1[300];vector<int>edge[500];int shuang;bool find(int k){ for(int p=0;p<edge[k].size();p++) { int v=edge[k][p]; if(vis[v]==shuang) continue; vis[v]=shuang; if(link1[v]==-1||find(link1[v])) { link1[v]=k; return 1; } } return 0;}bool H[300],L[300];int main(){ //freopen("//home/fpy/input.txt","r",stdin); while(scanf("%lld%lld%lld%lld%lld",&N,&M,&n,&m,&T)!=EOF) { for(int i=1;i<=N;i++) { scanf("%s",str[i]); for(int j=1;j<=M;j++) if(str[i][j-1]=='1') map[i][j]=1; else map[i][j]=0; } bool cao=false; b=0; if(m==n) { if(N==M) cao=true; else goto FUCK; } else b=(N*m-n*M)/(m-n); a=(M-b*(m+1))/m; if(!Judge() && !cao) { FUCK:; puts("-1"); continue; } long long ret=-1; for(b=1;b<=N/(n+1);b++) { if(!cao) b=(N*m-n*M)/(m-n); a=(M-b*(m+1))/m; if(a<b) break; if(Judge()) { long long ans=0; for(int j=1;j<=m+1;j++) { bool flag=false; for(int i=1;i<=n && !flag;i++) { for(int h=b+(i-1)*(a+b)+1;h<=b+(i-1)*(a+b)+a && !flag;h++) for(int l=(j-1)*(a+b)+1;l<=(j-1)*(a+b)+b && !flag;l++) if(0!=map[h][l]) flag=true; L[j]=flag; ans+=flag; } } for(int i=1;i<=n+1;i++) { bool flag=false; for(int j=1;j<=m && !flag;j++) { for(int h=(i-1)*(a+b)+1;h<=(i-1)*(a+b)+b && !flag;h++) for(int l=b+(j-1)*(a+b)+1;l<=b+(j-1)*(a+b)+a && !flag;l++) if(0!=map[h][l]) flag=true; H[i]=flag; ans+=flag; } } for(int i=1;i<=n;i++) for(int j=1;j<=m;j++) { bool flag=false; for(int h=b+(i-1)*(a+b)+1;h<=b+(i-1)*(a+b)+a && !flag;h++) for(int l=b+(j-1)*(a+b)+1;l<=b+(j-1)*(a+b)+a && !flag;l++) if(1!=map[h][l]) flag=true; ans+=flag; } int id=0; for(int i=1;i<=n+1;i++) { edge[i].clear(); if(!H[i]) for(int j=1;j<=m+1;j++) { if(L[j])continue; bool flag=false; for(int h=(i-1)*(a+b)+1;h<=(i-1)*(a+b)+b && !flag;h++) for(int l=(j-1)*(a+b)+1;l<=(j-1)*(a+b)+b && !flag;l++) if(0!=map[h][l]) flag=true; if(flag) edge[i].push_back(j); } } memset(vis,-1,sizeof(vis)); memset(link1,-1,sizeof(link1)); shuang=0; for(int i=1;i<=1+n;i++) { shuang++; if(find(i)) ans++; } if(ret==-1 || ret>ans) ret=ans; if(!cao) break; } if(!cao) break; } if(ret<0) puts("-1"); else printf("%lldn",ret*T); } return 0;}
