#include <bits/stdc++.h>
//#include <atcoder/modint>
//#include <atcoder/math>
//#include <boost/multiprecision/cpp_int.hpp>
//#include <ext/pb_ds/assoc_container.hpp>
//#include <ext/pb_ds/tree_policy.hpp>
#pragma GCC optimize("O3")
#define REP(i, n) for(int i = 0; i < n; i++)
#define REPP(i, n) for(int i = 1; i <= n; i++)
#define ALL(obj) (obj).begin(), (obj).end()
#define EPS (1e-9)
//#define INF (1e17)
#define PI (acos(-1))
//const double PI = acos(-1);
//const double EPS = 1e-15;
long long INF=(long long)1E17;
#define i_7 (long long)(1e9+7)
//#define i_7 998'244'353
long mod(long a){
    long long c = a % i_7;
    if(c >= 0) return c;
    return c + i_7;
}
long long po(long a, long b){
    if(b == 0) return 1;
    
    long long z = po(a , b / 2);
    z = mod(z * z);
    if(b % 2 != 0) z = mod(a * z);
    return z;
}

bool prime_(int n){
    if(n == 1){
        return false;
    }else if(n == 2){
        return true;
    }else{
        for(int i = 2; i <= std::sqrt(n); i++) if(n % i == 0) return false;
        return true;
    }
}

long long gcd_(long long a, long long b){
    if(a < b) std::swap(a,b);
    if(a % b == 0) return b;
    else return gcd_(b, a % b);
}

long long lcm_(long long x, long long y){
    return (x / gcd_(x,y)) * y;
}

using namespace std;
//using namespace atcoder;
//using mint = modint1000000007;
//using mint = modint998244353;
//using namespace boost::multiprecision;
//using namespace __gnu_pbds;

vector<vector<int>> G;
int main(){
  //using namespace std;
  int n, m;
  cin>>n>>m;
  G.resize(n);
  if(m > 0){
    int a[m], b[m];
    REP(i, m){
      cin>>a[i]>>b[i];
      a[i]--; b[i]--;
      G[a[i]].push_back(b[i]);
      G[b[i]].push_back(a[i]);
    }
  }
  int k;
  cin>>k;
  int c[k];
  REP(i, k){
    cin>>c[i];
    c[i]--;
  }
  
  if(m == 0){
    if(k == 1) cout << 1 << endl;
    else cout << -1 << endl;
    return 0;
  }
  vector<vector<long long>> dist(k, vector<long long>(n, INF));
  //memset(dist, INF, sizeof(dist));
  //bool used[n];
  vector<bool> used;
  REP(i, k){
    //memset(used, false, sizeof(used));
    used = vector<bool>(n, false);
    typedef pair<long long, int> P;
    priority_queue<P, vector<P>, greater<P>> q;
    q.emplace(0, c[i]);
    while(!q.empty()){
      P now = q.top();
      q.pop();
      int u = now.second;
      long long d = now.first;
      if(used[u]) continue;
      dist[i][u] = d;
      used[u] = true;
      for(int v: G[u]){
        if(used[v]) continue;
        q.emplace(d + 1, v);
      }
    }
  }
  
  vector<vector<long long>> dp(k, vector<long long>(1<<k, -1));
  REP(i, k) dp[i][1<<i] = 1;
  REP(x, 1<<k){
    //cout << "x: " << bitset<3>(x) << endl;
    REP(i, k){
      if(dp[i][x] < 0) continue;
      if(!(x>>i&1)) continue;
      REP(j, k){
        if(dist[i][c[j]] == INF) continue;
        int nx = (x | (1<<j));
        //cout << "nx: " << bitset<3>(nx) << endl;
        if(dp[j][nx] < 0) dp[j][nx] = dp[i][x] + dist[i][c[j]];
        else dp[j][nx] = min(dp[j][nx], dp[i][x] + dist[i][c[j]]);
      }
    }
    //cout << bitset<3>(x) << ": " <<  dp[x] << endl;
  }
  long long ans = -1;
  REP(i, k){
    if(dp[i][(1<<k) - 1] < 0) continue;
    if(ans < 0) ans = dp[i][(1<<k) - 1];
    else ans = min(ans, dp[i][(1<<k) - 1]);
  }
  cout << ans << endl;    
  return 0;
}
#include<bits/stdc++.h>

using namespace std;
typedef long long ll;

#define rep(i,n) for (long long i = 0; i < (n); ++i)
#define INF LONG_MAX/3
//#define DIV 1000000007
//#define DIV 998244353

template<class T>bool chmax(T &a, const T &b) { if (a<b) { a=b; return 1; } return 0; }
template<class T>bool chmin(T &a, const T &b) { if (b<a) { a=b; return 1; } return 0; }
int dx[4]={1,0,-1,0};
int dy[4]={0,1,0,-1};

ll A[505][505];
ll B[505][505];
ll dis[505][505][2];

int main(){
	ll R, C;

	cin >> R >> C;
	rep(i, R) rep(j, C-1) cin >> A[i][j];
	rep(i, R-1) rep(j, C) cin >> B[i][j];

	//cost, y, x, uemode
	priority_queue<tuple<ll, ll, ll, bool>, vector<tuple<ll, ll, ll, bool>>, greater<tuple<ll, ll, ll, bool> > >Q;
	Q.push({0, 0, 0, false});

	rep(i, R) rep(j, C) dis[i][j][0] = -1;
	rep(i, R) rep(j, C) dis[i][j][1] = -1;

	while(!Q.empty()) {
		ll cost, y, x;
		bool uemode;
		tie(cost, y, x, uemode) = Q.top();
		Q.pop();
		if(dis[y][x][uemode] != -1) continue;
		dis[y][x][uemode] = cost;

		if(y == R - 1 && x == C - 1) {
			cout << cost << endl;
			return 0;
		}

		//1
		if(x + 1 < C) {
			Q.push({cost + A[y][x], y, x+1, false});
		}

		//2
		if(x > 0) {
			Q.push({cost + A[y][x-1], y, x-1, false});
		}

		//3
		if(y + 1 < R) {
			Q.push({cost + B[y][x], y+1, x, false});
		}

		//4
		if(uemode && y > 0) {
			Q.push({cost + 1, y-1, x, uemode});
		}
		if(!uemode) {
			Q.push({cost + 1, y, x, true});
		}
	}



}
