#include <bits/stdc++.h>
using namespace std;
const int N = 1010,M = 2 * N * N;

int n,m,cnt;
int p[N*N],id[N][N];
struct Edge {
    int a,b,w;
}edge[M];
int dx[]={-1,0,1,0},dy[]={0,1,0,-1},dw[]={1,2,1,2};

int find(int x) {
    if(p[x] != x) p[x] = find(p[x]);
    return p[x];
}

void solve() {
    for(int z = 0; z < 2; z ++)
        for(int i = 1; i <= n; i ++)
            for (int j = 1; j <= m; j ++)
                for (int u = 0; u < 4; u ++) {
                    if(u % 2 == z) {
                        int x = i+dx[u],y = j+dy[u],w = dw[u];
                        if(x&&x<=n&&y&&y<=m) {
                            int a = id[i][j],b = id[x][y];
                            if(a < b) edge[cnt++] = {a,b,w};
                        }
                    }
                }
}

int main() {
    int t = 1;
    cin >> n >> m;
    for (int i = 1; i <= n; i ++) {
        for (int j = 1; j <= m; j ++) id[i][j] = t++;
    }

    for (int i = 1; i <= t; i ++) p[i] = i;

    int x1,y1,x2,y2;
    while(cin>>x1>>y1>>x2>>y2) {
        int a = id[x1][y1],b = id[x2][y2];
        p[find(a)] = find(b);
    }

    solve();

    int res = 0;
    for (int i = 0; i < cnt; i ++) {
        int a = find(edge[i].a),b = find(edge[i].b),w = edge[i].w;
        if(a != b) {
            p[a] = b;
            res += w;
        }
    }

    cout << res << endl;
    return 0;
}

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

const int N = 2010, M = 10010;

int n, m;
struct Edge
{
    int a, b, w;
}edge[M];
int p[N];

bool cmp(Edge x,Edge y) {
    return x.w < y.w;
}

int find(int x)
{
    if (p[x] != x) p[x] = find(p[x]);
    return p[x];
}

int main()
{
    cin >> n >> m;
    for (int i = 1; i <= n; i ++ ) p[i] = i;

    int res = 0, k = 0;
    for (int i = 0; i < m; i ++ )
    {
        int t, a, b, w;
        cin >> t >> a >> b >> w;
        if (t == 1)
        {
            res += w;
            p[find(a)] = find(b);
        }
        else edge[k ++ ] = {a, b, w};
    }

    sort(edge, edge + k,cmp);

    for (int i = 0; i < k; i ++ )
    {
        int a = find(edge[i].a), b = find(edge[i].b), w = edge[i].w;
        if (a != b)
        {
            p[a] = b;
            res += w;
        }
    }

    cout << res << endl;
    return 0;
}

#include <bits/stdc++.h>
using namespace std;
const int N = 16010;

int n,m;
int p[N];

struct Edge {
    int a,b,w;
}edge[N];

void init() {
    for (int i = 1; i <= n; i ++) p[i] = i;
}

bool cmp(Edge x,Edge y) {
    return x.w < y.w;
}

int find(int x) {
    if(p[x] != x) p[x] = find(p[x]);
    return p[x];
}

void kruskal() {
    init();
    int cnt = 0,res = -0x3f3f3f3f;
    for (int i = 0; i < m; i ++) {
        int a = edge[i].a,b = edge[i].b,w = edge[i].w;
        a = find(a),b = find(b);
        if(a != b) {
            p[a] = b;
            cnt++;
            res = max(res,w);
        }
    }

    printf("%d %d\n",cnt,res);
}

int main() {
    cin >> n >> m;
    for (int i = 0; i < m; i ++) scanf("%d%d%d",&edge[i].a,&edge[i].b,&edge[i].w);
    sort(edge,edge+m,cmp);
    kruskal();
    return 0;
}

#include <bits/stdc++.h>
using namespace std;
const int N = 110;

int n,a[N];
int dp1[N],dp2[N];

int main() {
    cin >> n;
    for (int i = 1; i <= n; i ++) cin >> a[i];

    for (int i = 1; i <= n; i ++) {
        dp1[i] = 1;
        for (int j = 1; j < i; j ++)
        if(a[i] > a[j]) dp1[i] = max(dp1[i],dp1[j]+1);
    }

    for (int i = n; i >= 1; i --) {
        dp2[i] = 1;
        for (int j = n; j > i; j --)
        if(a[i] > a[j]) dp2[i] = max(dp2[i],dp2[j]+1);
    }

    int res = -0x3f3f3f3f;
    for (int i = 1; i <= n; i ++) res = max(res,dp1[i]+dp2[i]-1);
    cout << n-res << endl;
    return 0;
}

#include <bits/stdc++.h>
using namespace std;
const int N = 210;

int n,k,cnt;
int p[N];

struct Edge {
    int a,b,w;
}edge[N];

bool cmp(Edge x,Edge y) {
    return x.w < y.w;
}

int find(int x) {
    if(p[x] != x) p[x] = find(p[x]);
    return p[x];
}

int kruskal() {
    for (int i = 1; i <= n; i ++) p[i] = i;
    for (int i = 1; i <= k; i ++) {
        int a = edge[i].a,b = edge[i].b,w = edge[i].w;
        a = find(a),b = find(b);
        if(a != b) {
            p[a] = b;
            cnt -= w;
            //cout<<"cnt = "<<cnt<<endl;
        }
    }
    return cnt;
}

int main() {
    cin >> n >> k;
    for (int i = 1; i <= k; i ++) cin>>edge[i].a>>edge[i].b>>edge[i].w,cnt += edge[i].w;
    sort(edge+1,edge+k+1,cmp);
    printf("%d\n",kruskal());
    return 0;
}

#include <bits/stdc++.h>
using namespace std;
const int N = 1e5+10;

int n,a[N];
int s1,s2;

int main() {
    cin >> n;
    for (int i = 0; i < n; i ++) scanf("%d",&a[i]);
    sort(a,a+n);
    for (int i = 0; i <= n/2-1; i ++ ) s1 += a[i];
    for (int i = n/2; i < n; i ++ ) s2 += a[i];
    if(n & 1) {
        printf("1 %d\n",s2-s1);
    }
    else {
        printf("0 %d\n",s2-s1);
    }
}

#include <bits/stdc++.h>
using namespace std;
const int N = 1010,INF = 0x3f3f3f3f;
typedef long long LL;
int ans = INF;
int a[N];

int main() {
    int n;
    cin >> n;
    for (int i = 0; i < n; i ++) cin >> a[i];
    for (int i = 0; i <= 83; i ++) {
        int l = i,r = i+17,t = 0;
        for (int j = 0; j < n; j ++) {
            if(a[j] < l) t += (l-a[j])*(l-a[j]);
            else if(a[j] > r) t += (a[j]-r)*(a[j]-r);
        }
        ans = min(ans,t);
    }
    cout<<ans<<endl;
    return 0;
}

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

LL res = 1;

int main() {
    int n;
    cin >> n;
    for (int i = 2; i <= n; i ++) {
        res *= i;
        while(res%10==0) res/=10;
        res = res%1000000;
    }
    cout << res%10 << endl;
}

#include <bits/stdc++.h>
using namespace std;
const int N = 10010;
typedef long long LL;

int n,m;
int a[N];
LL dp[N];

int main() {
    cin >> n >> m;
    for (int i = 1; i <= n; i ++) cin >> a[i];
    dp[0] = 1;
    for (int i = 1; i <= n; i ++) {
        for (int j = 0; j <= m; j ++)
        if(j >= a[i]) dp[j] += dp[j-a[i]];
    }
    cout<<dp[m]<<endl;
    return 0;
}

#include <bits/stdc++.h>
using namespace std;
const int N = 10010,M = 20010;
int n,m;
int h[N],idx;
int d[N],cnt[N];
int q[N];

struct Edge {
    int next,to;
}edge[M];

void add(int a,int b) {
    edge[idx].to = b;
    edge[idx].next = h[a];
    h[a] = idx++;
}

bool topsort() {
   int hh = 0,tt = -1;
   for (int i = 1; i <= n; i ++) {
       if(!d[i]) q[++tt] = i;
   }

   while(hh<=tt) {
       int t = q[hh++];
       for (int i = h[t]; ~i; i = edge[i].next) {
           int j = edge[i].to;
           d[j]--;
           if(!d[j]) q[++tt] = j;
       }
   }

   return tt == n-1;
}

int main() {
    memset(h,-1,sizeof h);
    cin >> n >> m;
    while(m -- ) {
        int a,b;
        cin >> a >> b;
        add(b,a);
        d[a]++;
    }

    if(!topsort()) puts("Poor Xed");
    else {
        for (int i = 1; i <= n; i ++) cnt[i] = 100;
        for (int i = 0; i < n; i ++ )
        {
            int j = q[i];
            for (int k = h[j]; ~k; k = edge[k].next)
                cnt[edge[k].to] = max(cnt[edge[k].to], cnt[j] + 1);
        }

        int res = 0;
        for (int i = 1; i <= n; i ++ ) res += cnt[i];
        cout<<res<<endl;
    }
    return 0;
}