# Find the maximum sum of elements in an array given that elements included in
# the sum must not be adjacent, horizontally, vertically or diagonally.

# Backtracking search was too slow.

# This program uses dynamic programming.

def validsubsets(n):
    def loop(m, odds, evens):
        if m == n: return odds+evens
        return(loop(m+1, [i*2+1 for i in evens], [i*2 for i in evens+odds]))
    return loop(1, [1], [0])

def compat(r1, r2):
    r2 = r2<<1 | r2 | r2>>1 # one's in all bits where r1 must not have a 1
    return (r1 ^ r2) == (r1 | r2)

def subsetvalue(subset, row):
    sum = 0
    for index in range(len(row)):
        if subset % 2: sum += row[index]
        subset >>= 1
    return sum

def subsetvalues(subsets, row):
    l = [(s,subsetvalue(s,row)) for s in subsets]
    l.sort(key=(lambda (s,v): -v))
    return l

def bestcompatval((currSubset, currVal), prev):
    for (prevSubset, prevVal) in prev:
        if compat(currSubset, prevSubset): return (currSubset, prevVal+currVal)
    return (currSubset, 0) 

def solve(M):
    nrows = len(M)
    ncols = len(M[0]) # assume all rows are same length
    vs = validsubsets(ncols)
    prev = subsetvalues(vs, M[0])
    for i in range(1, nrows):
        currRowVals = subsetvalues(vs, M[i])
        prev = [bestcompatval(currRowVal, prev) for currRowVal in currRowVals]
        prev.sort(key=(lambda (s,v): -v))
    return prev[0][1]
        

def test1(n):
    M = [ [1 for i in range(n)] for j in range(n) ]
    return solve(M)

def test2(n):
    M = [ [(n-i-1)*(n-j-1) for i in range(n)] for j in range(n) ]
    return solve(M)