Problem:
Planning Rolling Blackouts    Faced with seriously tight power supply-demand balance, the
electric power company for which you are working implemented rolling
    blackouts in this spring.  It divided the servicing area into several
groups of towns, and divided a day into several blackout periods.  At
each blackout period of a day, one of the groups, which alternates
from one group to another, is cut off the electricity.  By keeping the total demand of
electricity used by the rest of the towns within the supply
capacity, the company avoided unforeseeable large-scale blackout.    Working at the customer relations department, you had to listen to
so many complaints from the customers, which made you think that you
could have a better implementation.  Most of the complaints are about the
frequent cut-offs.  But you could have divided the area into a larger number of
groups, which resulted in less frequent cut-offs for each group.  The
other complaints are about the complicated grouping (in fact, someone
said that the shapes of the groups are fractals), which makes it
impossible to understand which town belongs to which group without
closely inspecting into the grouping list publicized by the company.
With the rectangular servicing area and towns located in a grid form,
you could have made a simpler grouping.    When you talked your analysis directly to the president of the company, you are
appointed to plan rolling blackouts for this summer.  Be careful what
you propose.  Anyway, you need to divide the servicing area into
as many groups as possible with keeping total demand of electricity
within the supply capacity.  It should also divide the towns into
simple and easy to remember groups.    Your task is to write a program, given a demand table (a table showing
electricity demand of each town) and the supply capacity, that answers
a grouping of towns that satisfy the following conditions.     The grouping should be made by horizontally or vertically splitting
    the area in a recursive manner.  In other words, the grouping must
    be a set of areas after applied the following splitting
    procedure to a set containing only the entire area for zero or
    more times: (The splitting procedure) remove one area from the set,
      either vertically or horizontally split it into two sub-areas,
      and put the sub-areas into the set.     The maximum suppressed demand of the grouping, which is the greatest total demand of the
    all but one group, is no more than the supply capacity.  The grouping has the largest number of groups among the groupings
    that satisfy the above conditions 1 and 2.  The grouping has the greatest amount of reserve power among the
  groupings that satisfy the above conditions 1, 2 and 3, where the
  reserve power of a grouping is the difference between the supply
  capacity and the maximum suppressed demand.     Note that the condition 1 does not allow such a grouping shown in Figure E-1.     Figure E-1: A grouping that violates the condition 1    Input   The input consists of one or more datasets.  Each dataset is given in
the following format.    h w s   u 11  u 12 ... u 1 w  u 21  u 22 ... u 2 w ...  u h 1  u h 2 ... u h w    The first line contains three positive integer numbers,
namely h , w and s , denoting the height and width
of the demand table and the power supply capacity.  The following h lines, each of which contains w integer numbers, denote demands of towns at respective
locations.  Those figures are constrained as follows.   1 ≤ h , w ≤ 32 1 ≤ u ij ≤ 100    Regrettably, you may assume that the supply capacity is less than the total demand of the area.    The last dataset is followed by a line containing three zeros.   Output   For each dataset, print a line having two integers indicating the
number of groups in the grouping that satisfies the conditions, and
the amount of the reserve power.  Each line should not have any
character other than those numbers and a space in between.   Sample Input  3 3 33
4 4 2
2 9 6
6 5 3
3 4 15
1 2 1 2
2 1 2 1
1 2 1 2
32 32 1112
1 1 1 1 2 1 1 1 1 1 1 1 2 1 1 1 1 1 1 1 1 2 1 1 1 1 1 1 1 1 1 1
1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 2 1 2 1 1 1 1 1 1 1 1 1 2
1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 2 1 1 1 1 1 1 1 1 1
2 1 1 2 1 1 1 1 1 1 1 2 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1
1 1 1 2 1 1 1 1 1 1 1 1 1 1 2 1 1 1 1 1 1 2 1 1 1 1 1 1 1 1 2 1
1 1 1 1 1 1 1 2 1 1 1 1 1 1 1 1 2 1 1 2 1 1 1 1 1 1 1 1 1 1 1 1
1 1 1 1 1 1 1 1 1 1 1 1 1 1 2 1 1 1 1 1 1 1 1 1 1 2 1 1 1 2 1 1
1 1 1 1 1 1 1 1 1 1 1 2 1 1 1 1 1 2 1 1 1 1 1 2 1 1 1 1 1 1 1 1
1 1 1 1 1 2 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1
1 1 1 1 1 2 2 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 2 1 2 1 1 1 1
1 1 1 1 1 1 1 1 1 1 2 2 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1
1 1 1 1 1 1 1 1 2 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1
1 1 1 2 1 1 1 1 1 1 2 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 2 1 1 1
1 1 1 1 1 2 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 2 1 1 1 1 1 1 1 1
2 1 1 1 1 1 1 1 1 1 1 1 1 2 1 1 1 1 1 2 1 1 1 1 1 2 1 1 1 1 1 1
1 1 1 1 1 1 1 1 1 1 1 2 1 2 1 2 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1
1 1 1 1 1 1 1 1 1 2 1 1 1 1 1 2 1 1 1 1 1 1 2 2 1 1 2 1 1 1 1 1
1 1 1 1 1 1 1 1 1 1 1 1 2 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1
2 1 1 1 1 2 1 1 1 1 1 1 1 1 1 1 1 2 1 1 1 1 1 2 1 1 1 1 1 1 1 1
1 1 1 1 1 1 1 1 1 1 2 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 2 1 1 1
2 1 1 1 1 1 1 1 2 1 1 1 2 2 2 1 1 2 1 1 1 1 1 1 1 1 1 1 1 1 1 1
1 1 1 1 1 1 2 1 1 1 1 1 1 1 1 1 1 1 2 1 1 1 1 1 1 1 1 1 1 1 1 1
1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1
1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 2 1 1 1 2 1 1 1 1 2 1 1
1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 2 1 1 1 1 1 1 1 2 1 1 1 2 1 1 1 1
1 1 1 1 1 1 1 1 1 1 1 1 2 1 1 1 1 1 1 1 1 1 1 1 2 2 1 1 1 1 2 2
1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1
1 1 1 1 1 1 1 1 1 1 2 1 1 1 1 1 1 1 1 1 1 1 1 1 1 2 1 2 1 1 1 1
1 1 1 1 1 1 1 1 2 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 2 1 1
1 1 1 2 1 1 2 1 1 1 2 1 2 1 1 1 1 1 1 1 2 2 1 1 1 1 1 1 2 1 1 1
1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 2 1 1 1 1 1 2 1 1 1 1 2 2 1
1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1
0 0 0  Output for the Sample Input  4 1
6 0
553 0

Solution (Python):
def calc(x1, y1, x2, y2):
    return S[y2-1][x2-1] - S[y1-1][x2-1] - S[y2-1][x1-1] + S[y1-1][x1-1]

INF = 10**18
def dfs(x1, y1, x2, y2):
    key = (x1, y1, x2, y2)
    if key in memo:
        return memo[key]
    val = calc(x1, y1, x2, y2)
    if val < rest:
        memo[key] = (0, -1)
        return (0, -1)
    res = (1, val)
    for i in xrange(x1+1, x2):
        k1, r1 = dfs(x1, y1, i, y2)
        k2, r2 = dfs(i, y1, x2, y2)
        if r1 >= 0 and r2 >= 0:
            res = max(res, (k1+k2, min(r1, r2)))
    for i in xrange(y1+1, y2):
        k1, r1 = dfs(x1, y1, x2, i)
        k2, r2 = dfs(x1, i, x2, y2)
        if r1 >= 0 and r2 >= 0:
            res = max(res, (k1+k2, min(r1, r2)))
    memo[key] = res
    return res

while 1:
    h, w, s = map(int, raw_input().split())
    if h == 0:
        break
    U = [map(int, raw_input().split()) for i in xrange(h)]
    S = [[0]*(w+1) for i in xrange(h+1)]
    su = sum(sum(e) for e in U)
    rest = su-s
    memo = {}
    for i in xrange(h):
        tmp = 0
        for j in xrange(w):
            tmp += U[i][j]
            S[i][j] = S[i-1][j] + tmp
    k, r = dfs(0, 0, w, h)
    print k, r - rest

Solution (Python):
from collections import defaultdict
def main(h, w, s):
    u = [None] * h
    acc = [None] * (h + 1)
    acc[0] = [0] * (w + 1)
    for i in range(h):
        x = list(map(int, input().split()))
        acc[i + 1] = [0] + x
        u[i] = x
    for i in range(h):
        acci1 = acc[i + 1]
        for j in range(w):
            acci1[j + 1] += acci1[j]
    for i in range(h):
        acci = acc[i]
        acci1 = acc[i + 1]
        for j in range(w):
            acci1[j + 1] += acci[j + 1]
    dp = defaultdict(int)
    allsum = acc[-1][-1]
    def accsum(l, r, d, u):
        return acc[u + 1][r + 1] - acc[u + 1][l] - acc[d][r + 1] + acc[d][l]
    for wm in range(w):
        for hm in range(h):
            for l in range(w - wm):
                r = l + wm
                for d in range(h - hm):
                    u = d + hm
                    ac = accsum(l, r, d, u)
                    res = [1, s - (allsum - ac)]
                    for mw in range(l, r):
                        tmp1 = dp[(l, mw, d, u)]
                        tmp2 = dp[(mw + 1, r, d, u)]
                        if tmp1[1] >= 0 and tmp2[1] >= 0:
                            tmp = [tmp1[0] + tmp2[0], min(tmp1[1], tmp2[1])]
                            if tmp[0] > res[0]:
                                res = tmp
                            elif tmp[0] == res[0] and tmp[1] > res[1]:
                                res = tmp
                    for mh in range(d, u):
                        tmp1 = dp[(l, r, d, mh)]
                        tmp2 = dp[(l, r, mh + 1, u)]
                        if tmp1[1] >= 0 and tmp2[1] >= 0:
                            tmp = [tmp1[0] + tmp2[0], min(tmp1[1], tmp2[1])]
                            if tmp[0] > res[0]:
                                res = tmp
                            elif tmp[0] == res[0] and tmp[1] > res[1]:
                                res = tmp
                    dp[(l, r, d, u)] = res
    print(*dp[(0, w - 1, 0, h - 1)])

if __name__ == '__main__':
    while 1:
        h, w, s = map(int, input().split())
        if h == w == s == 0:
            break
        main(h, w, s)

Solution (Python):
import math,string,itertools,fractions,heapq,collections,re,array,bisect,sys,random,time,copy,functools

sys.setrecursionlimit(10**7)
inf = 10**20
eps = 1.0 / 10**13
mod = 10**9+7
dd = [(-1,0),(0,1),(1,0),(0,-1)]
ddn = [(-1,0),(-1,1),(0,1),(1,1),(1,0),(1,-1),(0,-1),(-1,-1)]

def LI(): return [int(x) for x in sys.stdin.readline().split()]
def LI_(): return [int(x)-1 for x in sys.stdin.readline().split()]
def LF(): return [float(x) for x in sys.stdin.readline().split()]
def LS(): return sys.stdin.readline().split()
def I(): return int(sys.stdin.readline())
def F(): return float(sys.stdin.readline())
def S(): return input()
def pf(s): return print(s, flush=True)


class Ruiwa():
    def __init__(self, a):
        self.H = h = len(a)
        self.W = w = len(a[0])
        self.R = r = a
        for i in range(h):
            for j in range(1,w):
                r[i][j] += r[i][j-1]

        for i in range(1,h):
            for j in range(w):
                r[i][j] += r[i-1][j]

    def search(self, x1, y1, x2, y2):
        x2 -= 1
        y2 -= 1
        if x1 > x2 or y1 > y2:
            return 0

        r = self.R
        rr = r[y2][x2]
        if x1 > 0 and y1 > 0:
            return rr - r[y1-1][x2] - r[y2][x1-1] + r[y1-1][x1-1]
        if x1 > 0:
            rr -= r[y2][x1-1]
        if y1 > 0:
            rr -= r[y1-1][x2]

        return rr

def main():
    rr = []

    def f(h,w,s):
        a = [LI() for _ in range(h)]
        rui = Ruiwa(a)
        ss = rui.R[-1][-1] - s

        fm = {}
        def _f(x1,y1,x2,y2):
            key = (x1,y1,x2,y2)
            if key in fm:
                return fm[key]
            t = rui.search(x1,y1,x2,y2)
            if t < ss:
                fm[key] = (-1,-1)
                return (-1,-1)
            r = (1, t)
            for x in range(x1+1,x2):
                r1 = _f(x1,y1,x,y2)
                if r1[0] < 0:
                    continue
                r2 = _f(x,y1,x2,y2)
                if r2[0] < 0:
                    continue
                tr = (r1[0]+r2[0], min(r1[1], r2[1]))
                if r < tr:
                    r = tr
            for y in range(y1+1,y2):
                r1 = _f(x1,y,x2,y2)
                if r1[0] < 0:
                    continue
                r2 = _f(x1,y1,x2,y)
                if r2[0] < 0:
                    continue
                tr = (r1[0]+r2[0], min(r1[1], r2[1]))
                if r < tr:
                    r = tr
            fm[key] = r
            return r

        r,rs = _f(0,0,w,h)

        return '{} {}'.format(r, rs - ss)

    while 1:
        n,m,s = LI()
        if n == 0 and m == 0 and s == 0:
            break
        rr.append(f(n,m,s))
        

    return '\n'.join(map(str,rr))


print(main())