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

struct maca {int x,y,v;} g[2000];
int otac[50],mg[50][50],sg[255][1003],w[260][260];

int poredi(maca a,maca b)
{
    if(a.v<b.v) return 1;
    else return 0;
}


int nadji(int a)
{
    if(otac[a]==a) return a;
    else return otac[a]=nadji(otac[a]);
}


void spoj(int a,int b)
{
    int x,y;
    x=nadji(a);  y=nadji(b);

    if(rand()%2) otac[x]=y;
    else otac[y]=x;
}

void nsg(int vrsta,int cvor,int l,int d)
{
    int s=(l+d)/2;
    if(l==d)  sg[vrsta][cvor]=w[vrsta][l];
    else
    {
        nsg(vrsta,2*cvor,l,s);
        nsg(vrsta,2*cvor+1,s+1,d);
        sg[vrsta][cvor]=min(sg[vrsta][2*cvor],sg[vrsta][2*cvor+1]);
    }

}

int resi(int vv,int cvor,int l,int d,int x,int y)
{
    int s=(l+d)/2,r=70000;

    if(x<=l && y>=d) return sg[vv][cvor];
    else
    {
        if(l<=s)  r=resi(vv,2*cvor,l,s,x,y);
        if(d>s)   r=min(r,resi(vv,2*cvor+1,s+1,d,x,y));
        return r;
    }
}

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)
{
    int n=N,i,h,j,res,a,b,vr,x1,x2,y1,y2,u,glava;

    if(N==2)
    {


        for(i=1;i<=R;i++)
        {
            for(j=1;j<=C;j++) w[i][j]=W[i][j];
            nsg(i,1,1,C);
        }


        for(h=1;h<=Q;h++)
       {
           res=70000;
           x1=X1[h]; x2=X2[h];  y1=Y1[h];  y2=Y2[h];

           for(i=x1;i<=x2;i++)
           {
             res=min(res,resi(i,1,1,C,y1,y2));
           }

           O[h]=res;
       }
    }
    else
    {
        for(i=1;i<=Q;i++) O[i]=0;
       for(h=1;h<=Q;h++)
       {

          for(i=1;i<=N;i++)
          {
              for(j=1;j<=N;j++) mg[i][j]=-1;
          }

          x1=X1[h]; x2=X2[h];  y1=Y1[h];  y2=Y2[h];

          for(i=x1;i<=x2;i++)
          {
              for(j=y1;j<=y2;j++)
              {
                  a=U[i][j]; b=V[i][j]; vr=W[i][j];

                  if(mg[a][b]==-1)  mg[a][b]=vr;
                  else mg[a][b]=min(mg[a][b],vr);
              }
          }

          u=0;
          for(i=1;i<=n;i++)
          {
              for(j=1;j<=n;j++)
              {
                  if(mg[i][j]!=-1) {u++; g[u].x=i;  g[u].y=j; g[u].v=mg[i][j];}
              }
          }

          for(i=1;i<=n;i++) otac[i]=i;
          res=0;
          sort(g+1,g+u+1,poredi);

          for(i=1;i<=u;i++)
          {
              a=g[i].x;  b=g[i].y;
              if(nadji(a)!=nadji(b)) {spoj(a,b);  res+=g[i].v;}
          }

          glava=nadji(1);



          for(i=1;i<=n;i++)
          {
              if(nadji(i)!=glava) O[h]=-1;
          }

          if(O[h]==0)  O[h]=res;
       }
    }



}