#include <algorithm>
#include <bitset>
#include <cassert>
#include <cmath>
#include <functional>
#include <iomanip>
#include <iostream>
#include <map>
#include <queue>
#include <unordered_map>
#include <vector>
#include <string.h>
#include <set>

using namespace std;

#define COUT(x) cout << #x << " = " << (x) << " (L" << __LINE__ << ")" << endl

template<class T> void printvec(const vector<T>& v) {
  for (auto x : v) { cout << x << " "; }
  cout << endl;
}
template<class T> void printtree(const vector< vector<T> >& tree) {
  for (long long i = 0; i < tree.size(); ++i) {
    cout << i + 1 << ": "; printvec(tree[i]);
  }
}
template<class T, class U> void printmap(const map<T, U>& mp) {
  for (auto x : mp) { cout << x.first << "=>" << x.second << endl; }
}

template<class T> inline bool chmax(T& a, T b) { if (a < b) { a = b; return true; } return false; }
template<class T> inline bool chmin(T& a, T b) { if (a > b) { a = b; return true; } return false; }

#define rep(i, n) for(ll i = 0; i < n; ++i)
#define all(s) s.begin(), s.end()
#define fr first
#define sc second
#define mp make_pair
#define pb push_back

typedef long long ll;
typedef unsigned long long ull;
typedef pair<ll, ll> P;
typedef tuple<ll, ll, ll> triple;
typedef double D;

const ll INF = 1e9;
const ll MOD = 1000000007;  // 1e9 + 7

vector<vector<ll>> g;
vector<ll> dp; // -1 .. no paint, 0 .. red, 1 .. blue

// c .. 0 or 1
bool dfs(int v, int c) {
  if (dp[v] >= 0) {
    return dp[v] == c;
  }
  // Here, dp[v] == -1
  dp[v] = c;
  int nc = c^1; // next color
  for (auto nv : g[v]) {
    if (!dfs(nv, nc)) { return false; }
  }
  return true;
}

int main(int argc, char** argv) {
  cin.tie(NULL);
  cout.tie(NULL);
  ios_base::sync_with_stdio(false);
  //cout << setprecision(10) << fixed;

  ll n, m;
  cin >> n >> m;
  g.resize(n);
  dp.assign(n, -1);
  rep(i, m) {
    ll a, b;
    cin >> a >> b;
    --a; --b; //0-indexed
    g[a].push_back(b);
    g[b].push_back(a);
  }

  if (dfs(0, 0)) { // g is bipartite grah
    ll red = 0;
    rep(i, n) {
      if (dp[i] == 0) { ++red; }
    }
    ll blue = n-red;
    cout << red*blue - m << endl;
  } else {
    cout << n*(n-1)/2 - m << endl;
  }
}

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef long double ld;
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; }
const ll INF=1LL<<60;
const int inf=1<<30;
const int mod=1e9+7;
int main(){
    cin.tie(0);
    ios::sync_with_stdio(false);
    int h,w;cin >> h >> w;
    int a[h][w],b[h][w];
    for(int i=0;i<h;i++){
        for(int j=0;j<w;j++){
            cin >> a[i][j];
        }
    }
    for(int i=0;i<h;i++){
        for(int j=0;j<w;j++){
            cin >> b[i][j];
        }
    }
    const int vmax=12800;
    bool c[h][w][2*vmax]={false};
    c[0][0][a[0][0]-b[0][0]+vmax]=true;
    c[0][0][b[0][0]-a[0][0]+vmax]=true;
    for(int i=0;i<h;i++){
        for(int j=0;j<w;j++){
            for(int k=0;k<2*vmax;k++){
                if(!c[i][j][k]){
                    continue;
                }
                if(i<h-1){
                    c[i+1][j][k+a[i+1][j]-b[i+1][j]]=true;
                    c[i+1][j][k+b[i+1][j]-a[i+1][j]]=true;
                }
                if(j<w-1){
                    c[i][j+1][k+a[i][j+1]-b[i][j+1]]=true;
                    c[i][j+1][k+b[i][j+1]-a[i][j+1]]=true;
                }
            }
        }
    }
    int ans=inf;
    for(int i=0;i<2*vmax;i++){
        if(c[h-1][w-1][i]){
            chmin(ans,abs(i-vmax));
        }
    }
    cout << ans << endl;
}