# Task

John won the championship of a TV show. He can get some bonuses.

He needs to play a game to determine the amount of his bonus.

Here are `n` rows and `m` columns of cards were placed on the ground. A non-negative number is written on each card.

The rules of the game are:

- Player starts from the top-left coner, walk to the bottom-right coner. 

- Players can only walk downward or right. 

- The sum of the numbers collected by the players will be used as the bonus.

John has two chances to play this game on a game map. Specifically, when John finishes the game, the card on his path will be removed, and then he can walk again.

Your task is to help John calculate the maximum amount of bonuses he can get.

# Input

- `gameMap/gamemap`: A `n` x `m` integer array. Each element represents the number on the card.
  - `4 <= n,m <= 40(Pyhon)/100(JS)`


- All inputs are valid.

# Output

An integer. the maximum amount of bonuses John can get.

# Eaxmple

For 
```
gameMap=
[
[1, 3, 9],
[2, 8, 5],
[5, 7, 4]
]
```
The output should be `39`.

One of the possible solution is:
```
1st game:
[
[>, >, v],
[2, 8, v],
[5, 7, v]
]
1+3+9+5+4=22

2nd game:
[
[v, 0, 0],
[>, v, 0],
[5, >, >]
]
0+2+8+7+0=17

Final bonus = 22 + 17 = 39
```

Source: codewars | Difficulty: EASY
Tags: Dynamic programming

Starter code: def calc(gamemap):
	

Solutions:
def calc(gamemap):
	(nr, nc) = (len(gamemap), len(gamemap[0]))

	def _i(ra, rb):
		return ra * nr + rb
	(vs, ws) = ([0] * nr ** 2, [0] * nr ** 2)
	for s in range(nr + nc - 1):
		for ra in range(max(0, s - nc + 1), min(s + 1, nr)):
			for rb in range(ra, min(s + 1, nr)):
				ws[_i(ra, rb)] = gamemap[ra][s - ra] + (gamemap[rb][s - rb] if ra != rb else 0) + max((vs[_i(ra - da, rb - db)] for da in (0, 1) if da <= ra for db in (0, 1) if db <= rb))
		(vs, ws) = (ws, vs)
	return vs[-1]


from itertools import product
from functools import lru_cache

def calc(gamemap):

	@lru_cache(None)
	def calc0(p1, p2):
		((y1, x1), (y2, x2)) = (p1, p2)
		cost = gamemap[y1][x1]
		if p1 != p2:
			cost += gamemap[y2][x2]
		res = 0
		for ((dy1, dx1), (dy2, dx2)) in moves:
			p1 = (y1 + dy1, x1 + dx1)
			if p1 not in playground:
				continue
			p2 = (y2 + dy2, x2 + dx2)
			if p2 not in playground:
				continue
			r = calc0(p1, p2) if p1 < p2 else calc0(p2, p1)
			if r > res:
				res = r
		return cost + res
	playground = set(product(range(len(gamemap)), range(len(gamemap[0]))))
	moves = list(product(((0, 1), (1, 0)), repeat=2))
	return calc0((0, 0), (0, 0))


from itertools import combinations

def calc(gamemap):
	(x_max, y_max) = (len(gamemap) - 1, len(gamemap[0]) - 1)
	last_step = x_max + y_max - 1
	best_paths = {((0, 1), (1, 0)): gamemap[0][0] + gamemap[0][1] + gamemap[1][0] + gamemap[-2][-1] + gamemap[-1][-2] + gamemap[-1][-1]}
	for step in range(2, last_step):
		(new_best_paths, x_lower_limit, x_upper_limit) = ({}, max(0, step - y_max), min(step, x_max))
		for (x1, x2) in combinations(range(x_lower_limit, x_upper_limit + 1), 2):
			(y1, y2) = (step - x1, step - x2)
			previous_steps = set((((_x1, _y1), (_x2, _y2)) for (_x1, _y1) in ((x1 - 1, y1), (x1, y1 - 1)) for (_x2, _y2) in ((x2 - 1, y2), (x2, y2 - 1))))
			best_path_value = max([best_paths[points] for points in previous_steps if points in best_paths])
			new_best_paths[(x1, y1), (x2, y2)] = gamemap[x1][y1] + gamemap[x2][y2] + best_path_value
		best_paths = new_best_paths
	return max(best_paths.values())


from itertools import combinations

def calc(gamemap):
	(x_max, y_max) = (len(gamemap) - 1, len(gamemap[0]) - 1)
	last_step = x_max + y_max - 1
	dynamic_table = {((0, 1), (1, 0)): gamemap[0][0] + gamemap[0][1] + gamemap[1][0] + gamemap[-2][-1] + gamemap[-1][-2] + gamemap[-1][-1]}
	for step in range(2, last_step):
		_dynamic_table = {}
		x_lower_limit = max(0, step - y_max)
		x_upper_limit = min(step + 1, x_max + 1)
		for (x1, x2) in combinations(range(x_lower_limit, x_upper_limit), 2):
			(y1, y2) = (step - x1, step - x2)
			previous_steps = set()
			d1 = []
			if x1:
				d1.append((-1, 0))
			if y1:
				d1.append((0, -1))
			d2 = []
			if x2:
				d2.append((-1, 0))
			if y2:
				d2.append((0, -1))
			for (_dx1, _dy1) in d1:
				for (_dx2, _dy2) in d2:
					(_x1, _y1) = (x1 + _dx1, y1 + _dy1)
					(_x2, _y2) = (x2 + _dx2, y2 + _dy2)
					if _x1 != _x2:
						previous_steps.add(((_x1, _y1), (_x2, _y2)))
			best_path_value = max([dynamic_table[points] for points in previous_steps])
			_dynamic_table[(x1, y1), (x2, y2)] = gamemap[x1][y1] + gamemap[x2][y2] + best_path_value
		dynamic_table = _dynamic_table
	return max(dynamic_table.values())


def calc(gamemap):
	(nr, nc) = (len(gamemap), len(gamemap[0]))
	(vs, ws) = ([0] * nr ** 2, [0] * nr ** 2)
	vs[0] = gamemap[0][0]
	for s in range(nr + nc - 2):
		for ra in range(min(s + 1, nr)):
			ca = s - ra
			for rb in range(ra, min(s + 1, nr)):
				cb = s - rb
				v = vs[ra * nr + rb]
				for da in (0, 1):
					(ra_, ca_) = (ra + da, ca + (1 - da))
					if ra_ < nr and ca_ < nc:
						for db in (0, 1):
							(rb_, cb_) = (rb + db, cb + (1 - db))
							if rb_ < nr and cb_ < nc:
								v_ = v + gamemap[ra_][ca_] + (gamemap[rb_][cb_] if ra_ != rb_ else 0)
								ws[ra_ * nr + rb_] = max(ws[ra_ * nr + rb_], v_)
		(vs, ws) = (ws, vs)
	return vs[-1]


from itertools import combinations

def calc(game_map):
	rows = len(game_map)
	cols = len(game_map[0])
	states = {(1, 0, 1): game_map[0][0] + game_map[0][1] + game_map[1][0]}
	state_keys = []
	for diagonal in range(2, rows + cols - 1):
		min_row = max(0, diagonal - cols + 1)
		max_row = min(rows - 1, diagonal)
		row_codes = range(min_row, max_row + 1)
		for (row_cell_1, row_cell_2) in combinations(row_codes, 2):
			state_keys.append((diagonal, row_cell_1, row_cell_2))
	for (diagonal, row_cell_1, row_cell_2) in state_keys:
		prev_values = []
		if row_cell_1 > 0:
			prev_values.append(states[diagonal - 1, row_cell_1 - 1, row_cell_2 - 1])
		if row_cell_1 > 0 and row_cell_2 < diagonal:
			prev_values.append(states[diagonal - 1, row_cell_1 - 1, row_cell_2])
		if row_cell_2 > row_cell_1 + 1:
			prev_values.append(states[diagonal - 1, row_cell_1, row_cell_2 - 1])
		if row_cell_2 < diagonal:
			prev_values.append(states[diagonal - 1, row_cell_1, row_cell_2])
		prev_value = max(prev_values)
		col_cell_1 = diagonal - row_cell_1
		col_cell_2 = diagonal - row_cell_2
		new_value = prev_value + game_map[row_cell_1][col_cell_1] + game_map[row_cell_2][col_cell_2]
		states[diagonal, row_cell_1, row_cell_2] = new_value
	final_diagonal = (rows + cols - 3, rows - 2, rows - 1)
	return states[final_diagonal] + game_map[rows - 1][cols - 1]


def calc(Q):
	(H, W, M, N, G) = (len(Q), ~-len(Q[0]), [0] * len(Q) ** 2, [0] * len(Q) ** 2, lambda Q, S: M[H * Q + S])
	for S in range(1, ~-H + W):
		for V in range(max(0, S - W), min(-~S, H)):
			for B in range(-~V, min(-~S, H)):
				N[H * V + B] = Q[V][S - V] + Q[B][S - B] + max(G(V, B), G(~-V, B), G(V, ~-B), G(~-V, ~-B))
		(M, N) = (N, M)
	return Q[0][0] + Q[~-H][W] + G(~-~-H, ~-H)


def calc(mp):
	h = len(mp)
	w = len(mp[0])
	dp = [[[0 for j in range(h + 1)] for i in range(h + 1)] for k in range(h + w + 1)]
	for s in range(1, h + w + 1):
		for i1 in range(1, h + 1):
			j1 = s - i1 + 1
			if j1 > 0 and j1 <= w:
				for i2 in range(1, h + 1):
					j2 = s - i2 + 1
					if j2 > 0 and j2 <= w:
						dp[s][i1][i2] = max(dp[s - 1][i1][i2 - 1], dp[s - 1][i1 - 1][i2], dp[s - 1][i1 - 1][i2 - 1], dp[s - 1][i1][i2]) + mp[i1 - 1][j1 - 1] + mp[i2 - 1][j2 - 1]
						if i1 == i2:
							dp[s][i1][i2] -= mp[i1 - 1][j1 - 1]
	return dp[h + w - 1][h][h]