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

int par[44], kol[44];
void Clear() {
    fill(par, par+44, -1);
    fill(kol, kol+44, 1);
}
int Find(int x) {
    if (par[x] == -1)
        return x;
    return par[x] = Find(par[x]);
}
void Union(int a, int b) {
    int x = Find(a), y = Find(b);
    if (kol[x] <= kol[y]) {
        kol[y] += kol[x];
        kol[x] = 0;
        par[x] = y;
    }
    else {
        kol[x] += kol[y];
        kol[y] = 0;
        par[y] = x;
    }
}

const int mx = 255;
int levo[mx][mx][mx], gore[mx][mx][mx];
int sqr[mx][mx][mx];

int solve(int x, int y, int a, int b) {
    int d1 = a-x+1, d2 = b-y+1;
    if (d1 == d2) {
        return sqr[x][y][d1];
    }
    if (d1 < d2) {
        return sqr[x][y][d1] + solve(x, y + d1, a, b);
    }
    if (d1 > d2) {
        return sqr[x][y][d2] + solve(x + d2, y, a, b);
    }
}

void Resi(int N, int R, int C, int Q, int** U, int** V, int** W,
	int* X1, int* Y1, int* X2, int* Y2, int* O)
{

	if (N == 2) {

        for (int i = 1; i <= R; i++) {
            for (int j = 1; j <= C; j++) {
                levo[i][j][1] = gore[i][j][1] = W[i][j];
                for (int l = 2; l <= max(i, j); l++) {
                        if (l <= j)
                    levo[i][j][l] = min(W[i][j], levo[i][j-1][l-1]);
                        if (l <= i)
                    gore[i][j][l] = min(W[i][j], gore[i-1][j][l-1]);
                }
            }
        }

        for (int i = 1; i <= R; i++) {
            for (int j = 1; j <= C; j++) {
                sqr[i][j][1] = W[i][j];
                for (int d = 2; d <= min(R-i+1, C-j+1); d++) {
                    sqr[i][j][d] = min(sqr[i][j][d-1], min(levo[i+d-1][j+d-1][d], gore[i+d-1][j+d-1][d]));
                }
            }
        }


        for (int q = 1; q <= Q; q++) {
            O[q] = solve(X1[q], Y1[q], X2[q], Y2[q]);
        }

        return;
	}

	for (int q = 1; q <= Q; q++) {

        int ans = 0;
        Clear();

        priority_queue<pair<int, pair<int, int>>> pq;

        for (int i = X1[q]; i <= X2[q]; i++) {
            for (int j = Y1[q]; j <= Y2[q]; j++) {
                pq.push({-W[i][j], {U[i][j], V[i][j]}});
            }
        }

        while (!pq.empty()) {
            int w = -pq.top().first;
            int u = pq.top().second.first;
            int v = pq.top().second.second;
            pq.pop();

            if (Find(u) == Find(v))
                continue;

            ans += w;
            Union(u, v);
        }

        O[q] = -1;

        for (int i = 1; i <= N; i++) {
            if (kol[i] == N) {O[q] = ans; break;}
        }

	}
}