AOJ1176.cpp

#include <algorithm>
#include <cmath>
#include <climits>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <fstream>
#include <iostream>
#include <list>
#include <map>
#include <queue>
#include <set>
#include <sstream>
#include <stack>
#include <string>
#include <vector>
#include <cassert>
#include <functional>

using namespace std;

#define LOG(...) printf(__VA_ARGS__)
//#define LOG(...)
#define FOR(i,a,b) for(int i=(int)(a);i<(int)(b);++i)
#define REP(i,n) for(int i=0;i<(int)(n);++i)
#define ALL(a) (a).begin(),(a).end()
#define RALL(a) (a).rbegin(),(a).rend()
#define EXIST(s,e) ((s).find(e)!=(s).end())
#define SORT(c) sort((c).begin(),(c).end())
#define RSORT(c) sort((c).rbegin(),(c).rend())
#define CLR(a) memset((a), 0 ,sizeof(a))

typedef long long ll;
typedef unsigned long long ull;
typedef vector<bool> vb;
typedef vector<int> vi;
typedef vector<ll> vll;
typedef vector<vb> vvb;
typedef vector<vi> vvi;
typedef vector<vll> vvll;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;

const int dx[] = { -1, 0, 1, 0 }; const int dy[] = { 0, 1, 0, -1 };

struct UnionFind {
	vector<int> v;
	UnionFind(int n) : v(n)  { for (int i = 0; i < n; i++) v[i] = i; }
	int  find(int x)         { return v[x] == x ? x : v[x] = find(v[x]); }
	void unite(int x, int y) { v[find(x)] = find(y); }
};
int sum;
int h, w, s;
vvi cells;
vvi wa;
pii dp[32][32][32][32];
pii dfs(int lx,int ly,int rx,int ry) {
	if (dp[lx][ly][rx][ry].first != -1)
		return dp[lx][ly][rx][ry];
	int kukanwa = wa[ry][rx];
	if (ly - 1 >= 0)
		kukanwa -= wa[ly - 1][rx];
	if (lx - 1 >= 0)
		kukanwa -= wa[ry][lx - 1];
	if (ly - 1 >= 0&& lx - 1 >= 0)
		kukanwa += wa[ly - 1][lx - 1];
	pii res = {1,s-(sum-kukanwa)};
	if (res.second < 0)
		return{ -1e9,1e9 };
	//vdiv
	FOR(i, lx + 1, rx+1) {
		pii p1 = dfs(lx, ly, i-1, ry);
		pii p2 = dfs(i, ly, rx, ry);
		pii res2 = { p1.first + p2.first,min(p1.second,p2.second) };
		res = max(res, res2);
	}
	//hdiv
	FOR(i, ly + 1, ry + 1) {
		pii p1 = dfs(lx, ly, rx, i-1);
		pii p2 = dfs(lx, i, rx, ry);
		pii res2 = { p1.first + p2.first,min(p1.second,p2.second) };
		res = max(res, res2);
	}
	dp[lx][ly][rx][ry] = res;
	return res;
}
int main() {
	while (cin>>h>>w>>s,h) {
		sum=0;
		cells.clear();
		cells.resize(h, vi(w));
		REP(i, h) {
			REP(j, w) {
				cin >> cells[i][j];
				sum += cells[i][j];
			}
		}
		wa = cells;
		REP(i, h) {
			REP(j, w) {
				if (i != 0)
					wa[i][j] += wa[i - 1][j];
				if (j != 0)
					wa[i][j] += wa[i][j-1];
				if(i!=0&&j!=0)
					wa[i][j] -= wa[i-1][j - 1];
			}
		}
		REP(i, h)
			REP(j, w)
			REP(k, h)
			REP(l, w)
			dp[j][i][l][k] = {-1,0};
		pii p=dfs(0,0,w-1,h-1);
		cout << p.first << " " << p.second << endl;
	}
}