#include <bits/stdc++.h>
using namespace std;

fstream cinn,conn;

int n,m,k,mask[20],a,b;
char s;

int dp[20][1<<16];
bool li[20][1<<16];

vector< pair<int,int> > v[20];

int ff(int x,int m){
    if(x==n)return 0;
    
    if(li[x][m])return dp[x][m];
    li[x][m]=true;
    dp[x][m]=k;
    
    for(int i=0;i<k;i++){
        if(((1<<i)&m)==0 and ((1<<i)&mask[x])>0){
            dp[x][m]=min(dp[x][m],ff(x,m|(1<<i))+1);
        }
    }
    
    for(int i=0;i<v[x].size();i++){
        if((m|v[x][i].second)==m)dp[x][m]=min(dp[x][m],ff(v[x][i].first,m));
    }
    
    return dp[x][m];
}

int main() {
    
    cinn.open("fart.in",ios_base::in);
    conn.open("fart.out",ios_base::out);
    
    cinn>>n>>m>>k;
    
    for(int i=1;i<=n;i++){
        for(int f=1;f<=k;f++){
            cinn>>s;
            mask[i]*=2; mask[i]+=s-'0';
        }
    }
    
    for(int i=1;i<=m;i++){
        cinn>>a>>b;
        
        int res=0;
        for(int f=1;f<=k;f++){
            cinn>>s;
            res*=2; res+=s-'0';
        }
        
        v[a].push_back({b,res});
        v[b].push_back({a,res});
    }
    
    conn<<ff(1,0)<<"\n";


    return 0;
}