#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef long double ld;
typedef unsigned ui;
typedef unsigned long long ul;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;
typedef pair<ld, ld> pdd;
typedef pair<bool, bool> pbb;
typedef vector<int> vi;
#define pb push_back
#define fi first
#define se second
#define mid ((l + r) >> 1)
#define ls (i << 1)
#define rs (i << 1 | 1)
#define enum(i, j, k) for(int i = j; i <= (k); i ++)
#define open(i, j, k) for(int i = j; i <  (k); i ++)
#define dec(i, j, k)  for(int i = j; i >= (k); i --)
#define ae(x) for(node *p = h[x]; p; p = p->nxt)
#define fill(x, k) memset(x, k, sizeof x)
#define copy(x, y) memcpy(x, y, sizeof x)
#define fio(x) freopen(x".in", "r", stdin); freopen(x".out", "w", stdout);
template <class T> bool chkmin(T &x, T y)
{ return y < x ? (x = y , true) : false; }
template <class T> bool chkmax(T &x, T y)
{ return y > x ? (x = y , true) : false; }
void __init()
{
    ios::sync_with_stdio(false); cin.tie(0); cout.tie(0);
    cout << fixed << setprecision(16);
    srand(time(0) ^ ui(ul(new char)));
}
/* default code ends here */
const int maxn = 2e3 + 10;
int n, m, q;
int a[maxn][maxn], b[maxn][maxn], c[maxn][maxn];
int main()
{
	__init();
	cin >> n >> m >> q;
	string foo;
	enum(i, 1, n)
	{
		cin >> foo;
		enum(j, 1, m)
			a[i][j] = foo[j - 1] - '0';
	}
	/*enum(i, 1, n)
	{
		enum(j, 1, m)
			cerr << a[i][j] << ' ';
		cerr << endl;
	}*/
	enum(i, 1, n)
		enum(j, 2, m)
			b[i][j] = b[i - 1][j] + b[i][j - 1] - b[i - 1][j - 1] + bool(a[i][j] && a[i][j - 1]);
	/*enum(i, 1, n)
	{
		enum(j, 1, m)
			cerr << b[i][j] << ' ';
		cerr << endl;
	}*/
	enum(i, 2, n)
		enum(j, 1, m)
			c[i][j] = c[i - 1][j] + c[i][j - 1] - c[i - 1][j - 1] + bool(a[i][j] && a[i - 1][j]);
	enum(i, 1, n)
		enum(j, 1, m)
			a[i][j] += a[i - 1][j] + a[i][j - 1] - a[i - 1][j - 1];
	int x1, y1, x2, y2;
	while(q --)
	{
		cin >> x1 >> y1 >> x2 >> y2;
		//cerr << (a[x2][y2] - a[x2][y1 - 1] - a[x1 - 1][y2] + a[x1 - 1][y1 - 1]) << ' ' << (b[x2][y2] - b[x2][y1] - b[x1 - 1][y2] + b[x1 - 1][y1]) << ' ' << (c[x2][y2] - c[x2][y1 - 1] - c[x1][y2] + c[x1][y1 - 1]) << endl;
		cout << (a[x2][y2] - a[x2][y1 - 1] - a[x1 - 1][y2] + a[x1 - 1][y1 - 1]) - (b[x2][y2] - b[x2][y1] - b[x1 - 1][y2] + b[x1 - 1][y1]) - (c[x2][y2] - c[x2][y1 - 1] - c[x1][y2] + c[x1][y1 - 1]) << '\n';
	}
	return 0;
}

#include<bits/stdc++.h>
#define pb push_back
#define mp make_pair
#define fst first
#define snd second
using namespace std;

typedef long long ll;
typedef double db;
typedef long double ldb;

const int inf=1e9+10;
const int maxn=16;

int dp[1<<maxn][maxn],dp2[1<<maxn],n,m,cost[maxn][maxn]; 
vector <int> g[1<<maxn]; 

int main(){
	for(int i=0;i<maxn;i++) for(int j=0;j<maxn;j++) 
		cost[i][j]=0;
	scanf("%d%d",&n,&m);
	for(int i=0;i<m;i++){
		int u,v,c;
		scanf("%d%d%d",&u,&v,&c);
		u--; v--;
		cost[u][v]=c;
		cost[v][u]=c;
	}
	for(int mask=0;mask<(1<<n);mask++) 
		for(int i=0;i<n;i++) for(int j=0;j<n;j++)
			if((mask&(1<<i))&&(mask&(1<<j)))
				dp2[mask]=dp2[mask]+cost[i][j];
	for(int mask=0;mask<(1<<n);mask++) dp2[mask]=dp2[mask]/2;
	for(int mask=0;mask<(1<<n);mask++) for(int i=0;i<n;i++) dp[mask][i]=-inf;
	for(int mask=0;mask<(1<<n);mask++) if(mask&1) dp[mask][0]=dp2[mask];
	for(int mask=0;mask<(1<<n);mask++)
		for(int i=0;i<n;i++){
			if((dp[mask][i]==-inf)||!(mask&(1<<i))) continue;
			for(int mask2=(1<<n)-1-mask;mask2>0;mask2=(mask2-1)&((1<<n)-1-mask)){
				for(int j=0;j<n;j++){
					if(mask2&(1<<j)&&cost[i][j]>0){
						dp[mask|mask2][j]=max(dp[mask|mask2][j],dp[mask][i]+cost[i][j]+dp2[mask2]);
					}
				}
			}
		}
	printf("%d\n",dp2[(1<<n)-1]-dp[(1<<n)-1][n-1]);
	return 0;
}