#pragma clang optimize on
#include <cstdio>
#include <functional>
#include <iostream>
#include <queue>
#include <tuple>
#include <vector>
using namespace std;
using ll = long long;
#define shift 30

inline int get_digit() {
    int x = 0, f = 1;
    char c = getchar();
    while(c > '9' || c < '0') {
        if(c == '-') f = -1;
        c = getchar();
    }
    while(c >= '0' && c <= '9') {
        x = (x * 10) + (c ^ 48);
        c = getchar();
    }
    return x * f;
}

int main() {
    int R = get_digit(), C = get_digit();
    int A[250000], B[250000];
    int dist[500000], seen[500000], cost, pt, to_hide = R * C;
    vector<ll> s;
    s.reserve(2 * R * C);
    priority_queue<ll, vector<ll>, greater<ll>> queue(s.begin(), s.end());
    for(int i = 0; i < R * C; ++i)
        if(i % C != C - 1) A[i] = get_digit();
    for(int i = 0; i < (R - 1) * C; ++i) B[i] = get_digit();
    dist[0] = -10000000;
    queue.push((ll)(-10000000) << shift);
    while(queue.size()) {
        pt = queue.top() & ((1 << shift) - 1);
        if(pt == to_hide - 1) break;
        cost = queue.top() >> shift;
        queue.pop();
        seen[pt] = true;
        if(pt < to_hide) {
            if(!seen[pt + 1] && pt % C != C - 1) {
                if(cost + A[pt] < dist[pt + 1]) {
                    dist[pt + 1] = cost + A[pt];
                    queue.push(((ll)dist[pt + 1] << shift) | (pt + 1));
                }
            }
            if(!seen[pt - 1] && pt % C != 0) {
                if(cost + A[pt - 1] < dist[pt - 1]) {
                    dist[pt - 1] = cost + A[pt - 1];
                    queue.push(((ll)dist[pt - 1] << shift) | (pt - 1));
                }
            }
            if(!seen[pt + C] && pt < to_hide - C) {
                if(cost + B[pt] < dist[pt + C]) {
                    dist[pt + C] = cost + B[pt];
                    queue.push(((ll)dist[pt + C] << shift) | (pt + C));
                }
            }
            if(!seen[pt + to_hide] && cost + 1 < dist[pt + to_hide]) {
                dist[pt + to_hide] = cost + 1;
                queue.push(((ll)dist[pt + to_hide] << shift) | (pt + to_hide));
            }
        } else {
            if(to_hide < pt - C && !seen[pt - C] && cost + 1 < dist[pt - C]) {
                dist[pt - C] = cost + 1;
                queue.push(((ll)(cost + 1) << shift) | (pt - C));
            }
            if(!seen[pt - to_hide] && cost < dist[pt - to_hide]) {
                dist[pt - to_hide] = cost;
                queue.push(((ll)cost << shift) | (pt - to_hide));
            }
        }
    }
    printf("%d\n", dist[to_hide - 1] - dist[0]);
}
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int maxn = 555;

vector<int>G[22];
int ban[maxn];
int n, m;
set<int>se;
void dfs(int nowid, int sta) {
    if (nowid == n + 1) {
        se.insert(sta);
        return;
    }
    if (ban[nowid]) {
        dfs(nowid + 1, sta);
        return;
    }
    //不选
    dfs(nowid + 1, sta);
    //选
    for (int d : G[nowid])
        ban[d]++;
    dfs(nowid + 1, sta + (1 << nowid));
    for (int d : G[nowid])
        ban[d]--;
}


int del[22];
int vis[22];
//找有无奇环
int flag = 0;
int col[22];
void bfs(int nowid) {
    memset(col, -1, sizeof(col));
    col[nowid] = 0;
    queue<int>q;
    q.push(nowid);
    while (!q.empty()) {
        int nowid = q.front();
        vis[nowid] = 1;
        q.pop();
        for (int d : G[nowid]) {
            if (del[d])
                continue;
            if (col[d] == -1) {
                col[d] = col[nowid] ^ 1;
                q.push(d);
            }
            else if(col[d] == col[nowid]){
                flag = 1;
                return;
            }
        }
    }
}

void solve() {
    scanf("%d %d", &n, &m);
    for (int i = 1; i <= m; i++) {
        int a, b;
        scanf("%d %d", &a, &b);
        G[a].push_back(b);
        G[b].push_back(a);
    }
    dfs(1, 0);
    ll ans = 0;
    ll cnt = 0;

    //1号颜色
    for (int sta : se) {
        for (int i = 1; i <= n; i++) {
            if ((sta >> i) & 1)
                del[i] = 1;
            else
                del[i] = 0;
            vis[i] = 0;
        }
        cnt = 1ll;
        for (int i = 1; i <= n; i++) {
            if (vis[i] || del[i])
                continue;
            flag = 0;
            bfs(i);
            if (flag == 1) {
                cnt = 0;
                break;
            }
            cnt *= 2ll;
        }
        ans += cnt;
    }
    cout << ans << endl;
}

signed main() {
    // freopen("in.txt", "r", stdin);
    solve();
}
