#include <bits/stdc++.h>
using namespace std;
#define int int64_t
#define rep(i, a, b) for(int i = a; i < b; ++i)

int debug = 0;

const int N = 110;

int n, m, x[N], y[N], z[N], dp[1 << 19];

bool belong(int mask, int i) {
    return (mask >> i) & 1;
}

bool ok(int mask) {
    int k = (int)__builtin_popcount(mask);
    rep(i, 0, m) {
        if (k == x[i]) {
            int cnt = 0;
            rep(j, 0, n) if (belong(mask, j)) {
                cnt += (j + 1 <= y[i]);
            }
            if (cnt > z[i]) {
                return 0;
            }
        }
    }
    return 1;
}

main() {
    cin >> n >> m;
    rep(i, 0, m) {
        cin >> x[i] >> y[i] >> z[i];
    }
    dp[0] = 1;
    rep(mask, 1, (1 << n)) {
        if (ok(mask)) {
            rep(lst, 0, n) if (belong(mask, lst)) {
                dp[mask] += dp[mask ^ (1 << lst)];
            }
        }
    }
    cout << dp[(1 << n) - 1];
}
    #include <bits/stdc++.h>
    using namespace std;
    #include <math.h>
    #include <iomanip>
    #include <cstdint>
    #include <string>
    #include <sstream>
    template<class T> inline bool chmax(T& a, T b) { if (a < b) { a = b; return 1; } return 0; }
    template<class T> inline bool chmin(T& a, T b) { if (a > b) { a = b; return 1; } return 0; }
    #define rep(i,n) for (int i = 0; i < (n); ++i)
    typedef long long ll;
    using P=pair<ll,ll>;
    const int INF=1001001001;
    const int mod=998244353;
    
    struct edge{
      int to;
      ll w;
      edge(int to,ll w):to(to),w(w){}
    };

    int a[505][505],b[505][505];
    void solve(){
      int 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];
        }
      }
      int n=r*c;
      vector<vector<edge>>G(2*n);
      auto e=[&](int i,int j,int ni,int nj,int cost){
        int p=i*c+j,np=ni*c+nj;
        G[p].emplace_back(np,cost);
      };
      rep(i,r){
        rep(j,c){
          if(j+1<c){e(i,j,i,j+1,a[i][j]);}
          if(j-1>=0){e(i,j,i,j-1,a[i][j-1]);}
          if(i+1<r){e(i,j,i+1,j,b[i][j]);}
          e(i,j,i+r,j,1);
          e(r+i,j,i,j,0);
          if(i-1>=0){e(r+i,j,r+i-1,j,1);}
        }
      }
      priority_queue<P,vector<P>,greater<P>>q;
      vector<vector<int>>dist(2*r,vector<int>(c,INF));

      auto push=[&](int i,int j,int ni,int nj,int cost){
        if(chmin(dist[ni][nj],dist[i][j]+cost)){q.push({dist[ni][nj],ni*c+nj});}
      };

      q.push({0,0});
      dist[0][0]=0;
      while(!q.empty()){
        auto t=q.top();q.pop();
        int d=t.first,p=t.second;
        if(dist[p/c][p%c]!=d){continue;}
        for(auto u:G[p]){
          push(p/c,p%c,u.to/c,u.to%c,u.w);
        }
      }
      cout<<dist[r-1][c-1]<<endl;
    }
    int main(){
      ios_base::sync_with_stdio(false);
      cin.tie(NULL);
      solve();
      return 0;
    }