This is an easier version of the next problem. The difference is only in constraints.

You are given a rectangular $n \times m$ matrix $a$. In one move you can choose any column and cyclically shift elements in this column. You can perform this operation as many times as you want (possibly zero). You can perform this operation to a column multiple times.

After you are done with cyclical shifts, you compute for every row the maximal value in it. Suppose that for $i$-th row it is equal $r_i$. What is the maximal possible value of $r_1+r_2+\ldots+r_n$?


-----Input-----

The first line contains an integer $t$ ($1 \le t \le 40$), the number of test cases in the input.

The first line of each test case contains integers $n$ and $m$ ($1 \le n \le 4$, $1 \le m \le 100$) — the number of rows and the number of columns in the given matrix $a$. 

Each of the following $n$ lines contains $m$ integers, the elements of $a$ ($1 \le a_{i, j} \le 10^5$).


-----Output-----

Print $t$ integers: answers for all test cases in the order they are given in the input.


-----Example-----
Input
2
2 3
2 5 7
4 2 4
3 6
4 1 5 2 10 4
8 6 6 4 9 10
5 4 9 5 8 7

Output
12
29



-----Note-----

In the first test case, you can shift the third column down by one, this way there will be $r_1 = 5$ and $r_2 = 7$.

In the second case you can don't rotate anything at all, this way there will be $r_1 = r_2 = 10$ and $r_3 = 9$.

Difficulty: HARD
Tags: Bit manipulation

Sorting

Greedy algorithms

Complete search

Dynamic programming
Skill types: Bit manipulation

Sorting

Greedy algorithms

Complete search

Dynamic programming

Starter code:

Solutions:
for _ in range(int(input())):
	(N, M) = map(int, input().split())
	X = [[int(a) for a in input().split()] for _ in range(N)]
	Y = [[X[i][j] for i in range(N)] for j in range(M)]
	ma = 0
	dp = [[0] * (1 << N) for _ in range(M + 1)]
	for j in range(M):
		for mask in range(1 << N):
			maskpre = mask
			while maskpre >= 0:
				maskpre &= mask
				ma = 0
				for k in range(N):
					s = 0
					for i in range(N):
						if maskpre >> i & 1 == 0 and mask >> i & 1:
							s += X[i - k][j]
					ma = max(ma, s)
				dp[j + 1][mask] = max(dp[j + 1][mask], dp[j][maskpre] + ma)
				maskpre -= 1
	print(dp[-1][-1])


q = int(input())
for rquer in range(q):
	(c, r) = list(map(int, input().split()))
	matt = [list(map(int, input().split())) for i in range(c)]
	mat = [[matt[i][j] for i in range(c)] for j in range(r)]
	for i in range(r):
		mat[i].append(max(mat[i]))
		mat[i].reverse()
	mat.sort()
	mat.reverse()
	work = mat[:min(4, r)]
	for t in work:
		t.pop(0)
	r = min(4, r)
	wyn = 0
	for num in range(c ** r):
		shif = [num // c ** i % c for i in range(r)]
		new = 0
		for i in range(c):
			kol = [work[j][(i + shif[j]) % c] for j in range(r)]
			new += max(kol)
		wyn = max(wyn, new)
	print(wyn)


def solve(matrix, col, N, M):
	if col == M:
		ans = 0
		for row in matrix:
			if len(row) == 1:
				ans += row[0]
			else:
				ans += max(*row)
		return ans
	if N == 1:
		return solve(matrix, col + 1, N, M)
	ans = solve(matrix, col + 1, N, M)
	for _ in range(N - 1):
		tmp = matrix[0][col]
		for n in range(1, N):
			matrix[n - 1][col] = matrix[n][col]
		matrix[N - 1][col] = tmp
		local_ans = solve(matrix, col + 1, N, M)
		if local_ans > ans:
			ans = local_ans
	return ans

def main():
	T = int(input())
	for t in range(T):
		(N, M) = list([int(x) for x in input().split()])
		matrix = []
		for n in range(N):
			matrix.append(list([int(x) for x in input().split()]))
		elements = []
		for n in range(N):
			for m in range(M):
				elements.append((matrix[n][m], m))
		elements.sort(reverse=True)
		candidates = []
		for t in elements:
			if t[1] not in candidates:
				candidates.append(t[1])
				if len(candidates) == N:
					break
		simplified = []
		for n in range(N):
			row = []
			for m in candidates:
				row.append(matrix[n][m])
			simplified.append(row)
		ans = solve(simplified, 0, N, min(N, M))
		print(ans)
main()


import sys
input = sys.stdin.readline
t = int(input())
for testcases in range(t):
	(n, m) = list(map(int, input().split()))
	A = [list(map(int, input().split())) for i in range(n)]
	B = []
	for j in range(m):
		B.append([A[i][j] for i in range(n)])
	B.sort(key=lambda x: max(x), reverse=True)
	B = B[:n]
	LEN = len(B)
	if LEN == 1:
		print(sum(B[0]))
	elif LEN == 2:
		ANS = 0
		for i in range(n):
			A = 0
			for k in range(n):
				A += max(B[0][k], B[1][(i + k) % n])
			ANS = max(ANS, A)
		print(ANS)
	elif LEN == 3:
		ANS = 0
		for i in range(n):
			for j in range(n):
				A = 0
				for k in range(n):
					A += max(B[0][k], B[1][(i + k) % n], B[2][(j + k) % n])
				ANS = max(ANS, A)
		print(ANS)
	elif LEN == 4:
		ANS = 0
		for i in range(n):
			for j in range(n):
				for l in range(n):
					A = 0
					for k in range(n):
						A += max(B[0][k], B[1][(i + k) % n], B[2][(j + k) % n], B[3][(l + k) % n])
					ANS = max(ANS, A)
		print(ANS)


for _ in range(int(input())):
	(n, m) = map(int, input().split())
	a = [[int(x) for x in input().split()] for j in range(n)]
	x = [[a[i][j] for i in range(n)] for j in range(m)]
	x.sort(key=lambda xx: -max(xx))
	dp = [[0 for i in range(1 << n)] for j in range(m + 1)]
	an = 0
	for i in range(m):
		for prev in range(1 << n):
			for pres in range(1 << n):
				for j in range(n):
					ma = 0
					if prev ^ pres != prev + pres:
						continue
					for st in range(n):
						if pres & 1 << st:
							ma += x[i][(st + j) % n]
					dp[i + 1][pres ^ prev] = max(dp[i + 1][pres ^ prev], dp[i][prev] + ma)
	print(dp[m][(1 << n) - 1])


t = int(input())
for i in range(t):
	(n, m) = [int(item) for item in input().split()]
	mat = []
	col = [[] for _ in range(m)]
	for j in range(n):
		line = [int(item) for item in input().split()]
		for (k, item) in enumerate(line):
			col[k].append(item)
		mat.append(line)
	colmax = []
	for line in col:
		colmax.append([max(line), line])
	colmax.sort(reverse=True)
	colmax = colmax[:n]
	ans = 0
	for j in range(n ** (n - 1)):
		index = j
		rot = [0]
		for k in range(n - 1):
			rot.append(index % n)
			index //= n
		ret = 0
		for l in range(n):
			val = 0
			for k in range(len(colmax)):
				val = max(val, colmax[k][1][(l + rot[k]) % n])
			ret += val
		ans = max(ans, ret)
	print(ans)


import os, sys
from io import BytesIO, IOBase

def main():
	inf = -float('inf')
	for _ in range(int(input())):
		(n, m) = map(int, input().split())
		a = [list(map(int, input().split())) for _ in range(n)]
		y = 1 << n
		dp = [[0] + [inf] * (y - 1) for _ in range(m + 1)]
		for i in range(1, m + 1):
			for shift in range(n):
				for mask1 in range(y):
					for mask2 in range(y):
						new = mask1 ^ mask2
						if new & mask1:
							continue
						(mm, add) = (1, 0)
						for x in range(n):
							if mm & new:
								tt = x + shift
								if tt >= n:
									tt -= n
								add += a[tt][i - 1]
							mm <<= 1
						dp[i][mask2] = max(dp[i][mask2], dp[i - 1][mask1] + add)
		print(dp[m][y - 1])
BUFSIZE = 8192

class FastIO(IOBase):
	newlines = 0

	def __init__(self, file):
		self._fd = file.fileno()
		self.buffer = BytesIO()
		self.writable = 'x' in file.mode or 'r' not in file.mode
		self.write = self.buffer.write if self.writable else None

	def read(self):
		while True:
			b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
			if not b:
				break
			ptr = self.buffer.tell()
			(self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr))
		self.newlines = 0
		return self.buffer.read()

	def readline(self):
		while self.newlines == 0:
			b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
			self.newlines = b.count(b'\n') + (not b)
			ptr = self.buffer.tell()
			(self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr))
		self.newlines -= 1
		return self.buffer.readline()

	def flush(self):
		if self.writable:
			os.write(self._fd, self.buffer.getvalue())
			(self.buffer.truncate(0), self.buffer.seek(0))

class IOWrapper(IOBase):

	def __init__(self, file):
		self.buffer = FastIO(file)
		self.flush = self.buffer.flush
		self.writable = self.buffer.writable
		self.write = lambda s: self.buffer.write(s.encode('ascii'))
		self.read = lambda : self.buffer.read().decode('ascii')
		self.readline = lambda : self.buffer.readline().decode('ascii')
(sys.stdin, sys.stdout) = (IOWrapper(sys.stdin), IOWrapper(sys.stdout))
input = lambda : sys.stdin.readline().rstrip('\r\n')
main()


def main():
	t = int(input())
	for _ in range(t):
		(n, m) = map(int, input().split())
		l = []
		board = []
		for i in range(n):
			li = list(map(int, input().split()))
			board.append(li)
			for j in range(m):
				l.append((li[j], j))
		l.sort(key=lambda x: x[0], reverse=True)
		idxs = set()
		z = 0
		while len(idxs) < min(n, m):
			curr = l[z]
			idxs.add(curr[1])
			z += 1
		idxs = list(idxs)
		total = 0
		for i in range(n ** n):
			rotations = []
			num = i
			for j in range(n - 1, -1, -1):
				nj = n ** j
				q = num // nj
				num -= q * nj
				rotations.append(q)
			subtotal = 0
			for k in range(n):
				subtotal += max((board[(k + rotations[col]) % n][idxs[col]] for col in range(min(n, m))))
			total = max(total, subtotal)
		print(total)
main()


from sys import stdin

def f(lst, num):
	new = lst[num:] + lst[:num]
	return new
t = int(stdin.readline())
for i in range(t):
	(row, col) = tuple((int(x) for x in stdin.readline().split()))
	lst = list(([int(x)] for x in stdin.readline().split()))
	for j in range(row - 1):
		line = tuple((int(x) for x in stdin.readline().split()))
		for k in range(len(line)):
			lst[k].append(line[k])
	lst.sort(key=lambda x: max(x), reverse=True)
	ans = float('-inf')
	for a in range(4):
		for b in range(4):
			for c in range(4):
				for d in range(4):
					if col >= 1:
						aa = f(lst[0], a)
					else:
						aa = (0,) * row
					if col >= 2:
						bb = f(lst[1], b)
					else:
						bb = (0,) * row
					if col >= 3:
						cc = f(lst[2], c)
					else:
						cc = (0,) * row
					if col >= 4:
						dd = f(lst[3], d)
					else:
						dd = (0,) * row
					ans = max(ans, sum((max((x[j] for x in (aa, bb, cc, dd))) for j in range(row))))
	print(ans)


import os
import sys
from io import BytesIO, IOBase
BUFSIZE = 8192

class FastIO(IOBase):
	newlines = 0

	def __init__(self, file):
		self._fd = file.fileno()
		self.buffer = BytesIO()
		self.writable = 'x' in file.mode or 'r' not in file.mode
		self.write = self.buffer.write if self.writable else None

	def read(self):
		while True:
			b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
			if not b:
				break
			ptr = self.buffer.tell()
			(self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr))
		self.newlines = 0
		return self.buffer.read()

	def readline(self):
		while self.newlines == 0:
			b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
			self.newlines = b.count(b'\n') + (not b)
			ptr = self.buffer.tell()
			(self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr))
		self.newlines -= 1
		return self.buffer.readline()

	def flush(self):
		if self.writable:
			os.write(self._fd, self.buffer.getvalue())
			(self.buffer.truncate(0), self.buffer.seek(0))

class IOWrapper(IOBase):

	def __init__(self, file):
		self.buffer = FastIO(file)
		self.flush = self.buffer.flush
		self.writable = self.buffer.writable
		self.write = lambda s: self.buffer.write(s.encode('ascii'))
		self.read = lambda : self.buffer.read().decode('ascii')
		self.readline = lambda : self.buffer.readline().decode('ascii')
(sys.stdin, sys.stdout) = (IOWrapper(sys.stdin), IOWrapper(sys.stdout))
input = lambda : sys.stdin.readline().rstrip('\r\n')
from math import factorial
from collections import Counter, defaultdict, deque
from heapq import heapify, heappop, heappush

def RL():
	return map(int, sys.stdin.readline().rstrip().split())

def RLL():
	return list(map(int, sys.stdin.readline().rstrip().split()))

def N():
	return int(input())

def comb(n, m):
	return factorial(n) / (factorial(m) * factorial(n - m)) if n >= m else 0

def perm(n, m):
	return factorial(n) // factorial(n - m) if n >= m else 0

def mdis(x1, y1, x2, y2):
	return abs(x1 - x2) + abs(y1 - y2)
mod = 998244353
INF = float('inf')

def main():
	for _ in range(N()):
		(n, m) = RL()
		arr = []
		for _ in range(n):
			arr.append(RLL())
		larr = [list(i) for i in zip(*arr)]
		larr.sort(key=lambda a: max(a), reverse=1)
		larr = larr[:n]
		res = 0

		def dfs(lst, pos=0):
			nonlocal res
			if pos == min(n, len(larr)):
				res = max(res, sum(lst))
				return
			for i in range(n):
				nex = lst.copy()
				for j in range(n):
					nex[(i + j) % n] = max(nex[(i + j) % n], larr[pos][j])
				dfs(nex, pos + 1)
		dfs([0] * n)
		print(res)
main()


def naiveSolve():
	return

def main():
	t = int(input())
	allans = []
	for _ in range(t):
		(n, m) = readIntArr()
		grid = []
		for __ in range(n):
			grid.append(readIntArr())
		columns = []
		for col in range(m):
			temp = [grid[i][col] for i in range(n)]
			columns.append(temp)
		valCol = []
		for i in range(n):
			for j in range(m):
				valCol.append((grid[i][j], j))
		valCol.sort(reverse=True)
		topCols = set()
		for (val, col) in valCol:
			topCols.add(col)
			if len(topCols) == n:
				break
		m2 = len(topCols)
		grid2 = [[-1 for __ in range(m2)] for ___ in range(n)]
		topColsList = list(topCols)
		for j in range(m2):
			col = topColsList[j]
			for i in range(n):
				grid2[i][j] = grid[i][col]
		ans = -inf
		for mask in range(n ** m2):
			grid3 = [[-1 for __ in range(m2)] for ___ in range(n)]
			for col in range(m2):
				shift = mask % n
				for row in range(n):
					grid3[row][col] = grid2[(shift + row) % n][col]
				mask //= n
			tempAns = 0
			for row in range(n):
				maxx = -inf
				for col in range(m2):
					maxx = max(maxx, grid3[row][col])
				tempAns += maxx
			ans = max(ans, tempAns)
		allans.append(ans)
	multiLineArrayPrint(allans)
	return
import sys
input = sys.stdin.buffer.readline

def oneLineArrayPrint(arr):
	print(' '.join([str(x) for x in arr]))

def multiLineArrayPrint(arr):
	print('\n'.join([str(x) for x in arr]))

def multiLineArrayOfArraysPrint(arr):
	print('\n'.join([' '.join([str(x) for x in y]) for y in arr]))

def readIntArr():
	return [int(x) for x in input().split()]

def makeArr(defaultValFactory, dimensionArr):
	dv = defaultValFactory
	da = dimensionArr
	if len(da) == 1:
		return [dv() for _ in range(da[0])]
	else:
		return [makeArr(dv, da[1:]) for _ in range(da[0])]

def queryInteractive(r):
	print('? {}'.format(r))
	sys.stdout.flush()
	return readIntArr()

def answerInteractive(adj, n):
	print('!')
	for u in range(1, n + 1):
		for v in adj[u]:
			if v > u:
				print('{} {}'.format(u, v))
	sys.stdout.flush()
inf = float('inf')
MOD = 10 ** 9 + 7
from math import gcd, floor, ceil
for _abc in range(1):
	main()


rnd_mod = 1234567890133
rnd_x = 987654321098

def rnd():
	nonlocal rnd_x
	rnd_x = rnd_x ** 2 % rnd_mod
	return (rnd_x >> 5) % (1 << 20)

def randrange(a):
	return rnd() % a
T = int(input())
for _ in range(T):
	(N, M) = list(map(int, input().split()))
	X = []
	for __ in range(N):
		X.append([int(a) for a in input().split()])
	Y = [[X[i][j] for i in range(N)] for j in range(M)]
	ma = 0
	for t in range(577):
		for i in range(M):
			a = randrange(N)
			Y[i] = [Y[i][j - a] for j in range(N)]
		ma = max(ma, sum([max([Y[i][j] for i in range(M)]) for j in range(N)]))
	print(ma)


from random import randint
for _ in range(int(input())):
	(n, m) = map(int, input().split())
	A = [list(map(int, input().split())) for _ in range(n)]
	ans = 0
	for _ in range(100):
		for j in range(m):
			x = randint(0, n - 1)
			if x:
				B = []
				for i in range(n):
					B.append(A[i][j])
				B = B[x:] + B[:x]
				for i in range(n):
					A[i][j] = B[i]
		c = 0
		for i in range(n):
			c += max(A[i])
		ans = max(ans, c)
	print(ans)


import random
for _ in range(int(input())):
	(N, M) = map(int, input().split())
	X = [[int(a) for a in input().split()] for _ in range(N)]
	Y = [[X[i][j] for i in range(N)] for j in range(M)]
	ma = 0
	for t in range(99):
		for i in range(M):
			a = random.randrange(N)
			Y[i] = [Y[i][j - a] for j in range(N)]
		ma = max(ma, sum([max([Y[i][j] for i in range(M)]) for j in range(N)]))
	print(ma)


t = int(input())

def maxsa(A):
	ans = 0
	for i in range(n):
		cur_maxx = 0
		for j in range(4):
			cur_maxx = max(cur_maxx, A[j][i])
		ans += cur_maxx
	return ans

def fu(A):
	answer = 0
	for j in range(n):
		A[0] = A[0][1:] + A[0][:1]
		for i in range(n):
			A[1] = A[1][1:] + A[1][:1]
			for k in range(n):
				A[2] = A[2][1:] + A[2][:1]
				for l in range(n):
					A[3] = A[3][1:] + A[3][:1]
					cur_ans = maxsa(A)
					answer = max(answer, cur_ans)
	return answer
for j in range(t):
	(n, m) = map(int, input().split())
	A = [0] * n
	inds = [-1, -1, -1, -1]
	maxs = [0, 0, 0, 0]
	for j in range(n):
		A[j] = list(map(int, input().split()))
	for j in range(m):
		cur_maxs = 0
		for i in range(n):
			cur_maxs = max(cur_maxs, A[i][j])
		maxs.append(cur_maxs)
		inds.append(j)
		ind = 4
		while ind != 0 and maxs[ind] > maxs[ind - 1]:
			(inds[ind], inds[ind - 1]) = (inds[ind - 1], inds[ind])
			(maxs[ind], maxs[ind - 1]) = (maxs[ind - 1], maxs[ind])
			ind -= 1
		maxs.pop()
		inds.pop()
	S = [0] * 4
	for j in range(4):
		if inds[j] != -1:
			S[j] = [s[inds[j]] for s in A]
		else:
			S[j] = [0] * n
	print(fu(S))