A new gangster is trying to take control of the city. He makes a list of his $N$ adversaries (e.g. gangster $\mbox{1}$, gangster $2$, ... gangster $N-1$, gangster $N$) and plans to get rid of them.

$\mbox{K}$ mercenaries are willing to do the job. The gangster can use any number of these mercenaries. But he has to honor one condition set by them: they have to be assigned in such a way that they eliminate a consecutive group of gangsters in the list, e.g. gangster $\boldsymbol{i}$, gangster $i+1$, ..., gangster $j-1$, gangster $j$, where the following is true: $1\leq i\leq j\leq N$.

While our new gangster wants to kill all of them, he also wants to pay the least amount of money. All mercenaries charge a different amount to kill different people. So he asks you to help him minimize his expenses.  

Input Format

The first line contains two space-separated integers, $N$  and $\mbox{K}$. Then $\mbox{K}$ lines follow, each containing $N$ integers as follows:

The $j^{th}$ number on the $i^{th}$ line is the amount charged by the $i^{th}$mercenary for killing the $j^{th}$ gangster on the list.

Constraints

$1\leq N\leq20$
$1\leq K\leq10$
$0\leq amount$ $charged\leq10000$

Output Format

Just one line, the minimum cost for killing the $N$ gangsters on the list.

Sample Input
3 2
1 4 1
2 2 2

Sample Output
 5

Explanation

The new gangster can assign mercenary 1 to kill gangster 1, and mercenary 2 to kill gangster 2 and gangster 3.

Source: hackerrank | Difficulty: HARD
Tags: Dynamic programming


Solutions:
def bits_free(x, K):
	res = []
	for i in range(K):
		if x % 2 == 0:
			res.append(i)
		x //= 2
	return res
(N, K) = tuple((int(s) for s in input().strip().split()))
costs = []
for i in range(K):
	costs1 = [int(s) for s in input().strip().split()]
	costs.append(costs1)
dpmat = [[[1000000 for i in range(2 ** K)] for j in range(K)] for k in range(N)]
for mer in range(K):
	dpmat[0][mer][1 << mer] = costs[mer][0]
for gan in range(1, N):
	for lastmer in range(K):
		for mask in range(2 ** K):
			if dpmat[gan - 1][lastmer][mask] >= 1000000:
				continue
			dpmat[gan][lastmer][mask] = min(dpmat[gan][lastmer][mask], dpmat[gan - 1][lastmer][mask] + costs[lastmer][gan])
			for newmer in bits_free(mask, K):
				newmask = mask | 1 << newmer
				dpmat[gan][newmer][newmask] = min(dpmat[gan][newmer][newmask], dpmat[gan - 1][lastmer][mask] + costs[newmer][gan])
best = 1000000
for lastmer in range(K):
	for mask in range(2 ** K):
		if dpmat[N - 1][lastmer][mask] < 0:
			continue
		best = min(best, dpmat[N - 1][lastmer][mask])
print(best)


(G, M) = [int(s) for s in input().split()]
costs = list()
cache = dict()
for i in range(M):
	costs.append([int(s) for s in input().split()])

def kill(gn, imercs):
	key = str(gn) + str(imercs)
	if key in cache:
		return cache[key]
	mercs = imercs[:]
	if gn == 0:
		return 0
	temp = list()
	for m in mercs:
		tempm = mercs[:]
		tempm.remove(m)
		if len(tempm) == 0:
			temp.append(sum(costs[m][:gn]))
		else:
			for c in range(gn - 1, -1, -1):
				temp.append(sum(costs[m][c:gn]) + kill(c, tempm))
	cache[key] = min(temp)
	return min(temp)
print(str(kill(G, [i for i in range(M)])))


import itertools as it

def memoize(func):
	pool = {}

	def wrapper(*arg):
		if arg not in pool:
			pool[arg] = func(*arg)
		return pool[arg]
	return wrapper
(N, K) = map(int, input().split())
costs = [list(map(int, input().split())) for _ in range(K)]
csum = [list(it.accumulate(costs[y])) + [0] for y in range(K)]

@memoize
def solve(idx, mercs):
	res = 10 ** 9
	if idx == N:
		return 0
	for merc in mercs:
		rem_mercs = tuple((g for g in mercs if g != merc))
		for i in range(idx, N):
			curr = csum[merc][i] - csum[merc][idx - 1]
			assert curr == sum((costs[merc][c] for c in range(idx, i + 1)))
			res = min(res, curr + solve(i + 1, rem_mercs))
			if i == 0:
				res = min(res, solve(i, rem_mercs))
	return res
print(solve(0, tuple(range(K))))


import sys
(N, K) = map(int, sys.stdin.readline().split())
cost = []
MASK = 2 << K
INF = 10 ** 8 - 1
for i in range(K):
	prices = list(map(int, sys.stdin.readline().split()))
	prices.reverse()
	cost.append(prices)
dp = []
for i in range(MASK):
	dp.append([INF] * (N + 1))
dp[0][0] = 0

def hitman_available(hitman, mask):
	return not 2 << hitman & mask

def use_hitman(hitman, mask):
	return mask | 2 << hitman
for already_killed in range(N):
	for mask in range(MASK):
		for hitman in range(K):
			if hitman_available(hitman, mask):
				mask_after = use_hitman(hitman, mask)
				for num_to_kill in range(1, N - already_killed + 1):
					dp[mask_after][num_to_kill + already_killed] = min(dp[mask_after][num_to_kill + already_killed], dp[mask][already_killed] + sum(cost[hitman][already_killed:already_killed + num_to_kill]))
print(min((dp[i][N] for i in range(MASK))))


(N, K) = map(int, input().split())
cost = []
MASK = 2 << K
INF = 10 ** 8 - 1
for i in range(K):
	prices = list(map(int, input().split()))
	prices.reverse()
	cost.append(prices)
dp = []
for i in range(MASK):
	dp.append([INF] * (N + 1))
dp[0][0] = 0

def hitman_available(hitman, mask):
	return not 2 << hitman & mask

def use_hitman(hitman, mask):
	return mask | 2 << hitman
for already_killed in range(0, N):
	for mask in range(0, MASK):
		for hitman in range(0, K):
			if hitman_available(hitman, mask):
				mask_after = use_hitman(hitman, mask)
				for num_to_kill in range(1, N - already_killed + 1):
					dp[mask_after][num_to_kill + already_killed] = min(dp[mask_after][num_to_kill + already_killed], dp[mask][already_killed] + sum(cost[hitman][already_killed:already_killed + num_to_kill]))
print(min((dp[i][N] for i in range(MASK))))


(N, K) = map(int, input().strip().split())
prices = []
for prices_index in range(K):
	hitman_prices = []
	for price in map(int, input().strip().split()):
		hitman_prices.insert(0, price)
	prices.append(hitman_prices)
hit_perms = 2 << K
costs = []
for i in range(hit_perms):
	costs.append([10 ** 10] * (N + 1))
costs[0][0] = 0
for killed in range(N):
	for hit_perm in range(hit_perms):
		for hitman in range(K):
			if not 2 << hitman & hit_perm:
				hit_perm_after = hit_perm | 2 << hitman
				for num2kill in range(1, N - killed + 1):
					costs[hit_perm_after][num2kill + killed] = min(costs[hit_perm_after][num2kill + killed], costs[hit_perm][killed] + sum(prices[hitman][killed:killed + num2kill]))
print(min((costs[i][N] for i in range(hit_perms))))


import sys
(n, k) = map(int, input().split(' '))
cost_map = {}

def kill(start, killer_id, costs):
	if start == n:
		return 0
	min_cost = 1000111111
	i = 0
	for cost in costs:
		next_costs = list(costs)
		if cost[start] != -1:
			if killer_id != i and start != 0:
				next_costs[killer_id] = [-1] * n
			keys = [start + 1, i]
			for j in range(len(next_costs)):
				if next_costs[j][0] == -1:
					keys.append(j)
			key = ','.join([str(k) for k in keys])
			if key in cost_map:
				next_cost = cost_map[key]
			else:
				next_cost = kill(start + 1, i, next_costs)
				cost_map[key] = next_cost
			c = cost[start] + next_cost
			min_cost = min(min_cost, c)
		i += 1
	return min_cost
costs = []
for i in range(k):
	cost = [int(m) for m in input().split(' ')]
	costs.append(cost)
print(kill(0, 0, costs))


import heapq
(num_targets, num_mercs) = map(int, input().split())
costs = []
for _ in range(num_mercs):
	costs.append([int(i) for i in input().split()])
min_costs = [min([costs[m][t] for m in range(num_mercs)]) for t in range(num_targets)]

def get_mercs(bits):
	for i in range(num_mercs):
		if bits % 2 == 0:
			yield i
		bits //= 2

def get_neighbors(state):
	(cost, idx, mercs_used, using_merc) = state
	if using_merc >= 0:
		yield (cost + costs[using_merc][idx] - min_costs[idx], idx + 1, mercs_used, using_merc)
	for merc in get_mercs(mercs_used):
		if using_merc < 0 or costs[merc][idx] < costs[using_merc][idx]:
			yield (cost + costs[merc][idx] - min_costs[idx], idx + 1, mercs_used | 1 << merc, merc)
visited_set = set([])
frontier = [(sum(min_costs), 0, 0, -1)]
while len(frontier):
	state = heapq.heappop(frontier)
	if state in visited_set:
		continue
	visited_set.add(state)
	if state[1] == num_targets:
		print(state[0])
		break
	for neighbor in get_neighbors(state):
		if neighbor not in visited_set:
			heapq.heappush(frontier, neighbor)


from functools import lru_cache
(N, K) = map(int, input().split())
costs = [list(map(int, input().split())) for _ in range(K)]

@lru_cache(None)
def get_best(n, mask):
	if n == 0:
		return 0
	best = 1000000000000
	for i in range(K):
		if mask >> i & 1 == 1:
			n_mask = mask ^ 1 << i
			for j in range(n):
				best = min(best, get_best(j, n_mask) + sum(costs[i][j:n]))
	return best
print(get_best(N, 2 ** K - 1))


def bits_free(x, K):
	res = []
	for i in range(K):
		if x % 2 == 0:
			res.append(i)
		x //= 2
	return res
(N, K) = tuple((int(s) for s in input().strip().split()))
costs = []
for i in range(K):
	costs1 = [int(s) for s in input().strip().split()]
	costs.append(costs1)
dpmat = [[[1000000 for i in range(2 ** K)] for j in range(K)] for k in range(N)]
for mer in range(K):
	dpmat[0][mer][1 << mer] = costs[mer][0]
for gan in range(1, N):
	for lastmer in range(K):
		for mask in range(2 ** K):
			if dpmat[gan - 1][lastmer][mask] >= 1000000:
				continue
			dpmat[gan][lastmer][mask] = min(dpmat[gan][lastmer][mask], dpmat[gan - 1][lastmer][mask] + costs[lastmer][gan])
			for newmer in bits_free(mask, K):
				newmask = mask | 1 << newmer
				dpmat[gan][newmer][newmask] = min(dpmat[gan][newmer][newmask], dpmat[gan - 1][lastmer][mask] + costs[newmer][gan])
best = 1000000
for lastmer in range(K):
	for mask in range(2 ** K):
		if dpmat[N - 1][lastmer][mask] < 0:
			continue
		best = min(best, dpmat[N - 1][lastmer][mask])
print(best)


(N, K) = map(int, input().split())
cost = []
MASK = 2 << K
INF = 10 ** 8 - 1
for i in range(K):
	prices = [int(i) for i in input().split()]
	prices.reverse()
	cost.append(prices)
dp = []
for i in range(MASK):
	dp.append([INF] * (N + 1))
dp[0][0] = 0

def hitman_available(hitman, mask):
	return not 2 << hitman & mask

def use_hitman(hitman, mask):
	return mask | 2 << hitman
for already_killed in range(0, N):
	for mask in range(0, MASK):
		for hitman in range(0, K):
			if hitman_available(hitman, mask):
				mask_after = use_hitman(hitman, mask)
				for num_to_kill in range(1, N - already_killed + 1):
					dp[mask_after][num_to_kill + already_killed] = min(dp[mask_after][num_to_kill + already_killed], dp[mask][already_killed] + sum(cost[hitman][already_killed:already_killed + num_to_kill]))
print(min((dp[i][N] for i in range(MASK))))


inp = input('')
L = inp.split(' ')
L = [int(i) for i in L]
cost = []
for i in range(L[1]):
	a = input('')
	D = a.split(' ')
	D = [int(i) for i in D]
	cost.append(D)
k = L[1]
n = L[0]
if k == 1:
	print(sum(cost[0]))
else:
	m = 2 ** k
	M = [[[float('inf') for i in range(m)] for j in range(n + 1)] for K in range(k + 1)]
	miniac = float('inf')
	for j in range(1, n + 1):
		for i in range(1, 1 + k):
			M[i][1][2 ** (i - 1)] = cost[i - 1][0]
			for K in range(m):
				M[i][1][2 ** (i - 1)] = cost[i - 1][0]
				if K & 1 << i - 1 != 0:
					M[i][j][K] = cost[i - 1][j - 1] + min([M[x][j - 1][K & ~(1 << i - 1)] for x in range(1, k + 1) if x != i] + [M[i][j - 1][K]])
					if j == n:
						if M[i][j][K] < miniac:
							miniac = M[i][j][K]
	print(miniac)


(N, K) = map(int, input().split())
cost = []
MASK = 2 << K
INF = 10 ** 8 - 1
for i in range(K):
	prices = list(map(int, input().split()))
	prices.reverse()
	cost.append(prices)
dp = []
for i in range(MASK):
	dp.append([INF] * (N + 1))
dp[0][0] = 0

def hitman_available(hitman, mask):
	return not 2 << hitman & mask

def use_hitman(hitman, mask):
	return mask | 2 << hitman
for already_killed in range(0, N):
	for mask in range(0, MASK):
		for hitman in range(0, K):
			if hitman_available(hitman, mask):
				mask_after = use_hitman(hitman, mask)
				for num_to_kill in range(1, N - already_killed + 1):
					dp[mask_after][num_to_kill + already_killed] = min(dp[mask_after][num_to_kill + already_killed], dp[mask][already_killed] + sum(cost[hitman][already_killed:already_killed + num_to_kill]))
print(min((dp[i][N] for i in range(MASK))))


inp = input('')
L = inp.split(' ')
L = [int(i) for i in L]
cost = []
for i in range(L[1]):
	a = input('')
	D = a.split(' ')
	D = [int(i) for i in D]
	cost.append(D)
k = L[1]
n = L[0]
if k == 1:
	print(sum(cost[0]))
else:
	m = 2 ** k
	M = [[[float('inf') for i in range(m)] for j in range(n + 1)] for K in range(k + 1)]
	miniac = float('inf')
	for j in range(1, n + 1):
		for i in range(1, 1 + k):
			M[i][1][2 ** (i - 1)] = cost[i - 1][0]
			for K in range(m):
				M[i][1][2 ** (i - 1)] = cost[i - 1][0]
				if K & 1 << i - 1 != 0:
					M[i][j][K] = cost[i - 1][j - 1] + min([M[x][j - 1][K & ~(1 << i - 1)] for x in range(1, k + 1) if x != i] + [M[i][j - 1][K]])
					if j == n:
						if M[i][j][K] < miniac:
							miniac = M[i][j][K]
	print(miniac)


import sys
(N, K) = map(int, sys.stdin.readline().split())
cost = []
MASK = 2 << K
INF = 10 ** 8 - 1
for i in range(K):
	prices = list(map(int, sys.stdin.readline().split()))
	prices.reverse()
	cost.append(prices)
dp = []
for i in range(MASK):
	dp.append([INF] * (N + 1))
dp[0][0] = 0

def hitman_available(hitman, mask):
	return not 2 << hitman & mask

def use_hitman(hitman, mask):
	return mask | 2 << hitman
for already_killed in range(N):
	for mask in range(MASK):
		for hitman in range(K):
			if hitman_available(hitman, mask):
				mask_after = use_hitman(hitman, mask)
				for num_to_kill in range(1, N - already_killed + 1):
					dp[mask_after][num_to_kill + already_killed] = min(dp[mask_after][num_to_kill + already_killed], dp[mask][already_killed] + sum(cost[hitman][already_killed:already_killed + num_to_kill]))
print(min((dp[i][N] for i in range(MASK))))


import os
import sys
(N, K) = map(int, input().split())
cost = []
MASK = 2 << K
INF = 10 ** 8 - 1
for i in range(K):
	prices = list(map(int, input().split()))
	prices.reverse()
	cost.append(prices)
dp = []
for i in range(MASK):
	dp.append([INF] * (N + 1))
dp[0][0] = 0

def hitman_available(hitman, mask):
	return not 2 << hitman & mask

def use_hitman(hitman, mask):
	return mask | 2 << hitman
for already_killed in range(N):
	for mask in range(MASK):
		for hitman in range(K):
			if hitman_available(hitman, mask):
				mask_after = use_hitman(hitman, mask)
				for num_to_kill in range(1, N - already_killed + 1):
					dp[mask_after][num_to_kill + already_killed] = min(dp[mask_after][num_to_kill + already_killed], dp[mask][already_killed] + sum(cost[hitman][already_killed:already_killed + num_to_kill]))
print(min((dp[i][N] for i in range(MASK))))


import os
import sys
(N, K) = map(int, input().split())
cost = []
MASK = 2 << K
INF = 10 ** 8 - 1
for i in range(K):
	prices = list(map(int, input().split()))
	prices.reverse()
	cost.append(prices)
dp = []
for i in range(MASK):
	dp.append([INF] * (N + 1))
dp[0][0] = 0

def hitman_available(hitman, mask):
	return not 2 << hitman & mask

def use_hitman(hitman, mask):
	return mask | 2 << hitman
for already_killed in range(N):
	for mask in range(MASK):
		for hitman in range(K):
			if hitman_available(hitman, mask):
				mask_after = use_hitman(hitman, mask)
				for num_to_kill in range(1, N - already_killed + 1):
					dp[mask_after][num_to_kill + already_killed] = min(dp[mask_after][num_to_kill + already_killed], dp[mask][already_killed] + sum(cost[hitman][already_killed:already_killed + num_to_kill]))
print(min((dp[i][N] for i in range(MASK))))


import os
import sys
(N, K) = map(int, input().split())
cost = []
MASK = 2 << K
INF = 10 ** 8 - 1
for i in range(K):
	prices = list(map(int, input().split()))
	prices.reverse()
	cost.append(prices)
dp = []
for i in range(MASK):
	dp.append([INF] * (N + 1))
dp[0][0] = 0

def hitman_available(hitman, mask):
	return not 2 << hitman & mask

def use_hitman(hitman, mask):
	return mask | 2 << hitman
for already_killed in range(N):
	for mask in range(MASK):
		for hitman in range(K):
			if hitman_available(hitman, mask):
				mask_after = use_hitman(hitman, mask)
				for num_to_kill in range(1, N - already_killed + 1):
					dp[mask_after][num_to_kill + already_killed] = min(dp[mask_after][num_to_kill + already_killed], dp[mask][already_killed] + sum(cost[hitman][already_killed:already_killed + num_to_kill]))
print(min((dp[i][N] for i in range(MASK))))


import os
import sys
(N, K) = map(int, input().split())
cost = []
MASK = 2 << K
INF = 10 ** 8 - 1
for i in range(K):
	prices = list(map(int, input().split()))
	prices.reverse()
	cost.append(prices)
dp = []
for i in range(MASK):
	dp.append([INF] * (N + 1))
dp[0][0] = 0

def hitman_available(hitman, mask):
	return not 2 << hitman & mask

def use_hitman(hitman, mask):
	return mask | 2 << hitman
for already_killed in range(N):
	for mask in range(MASK):
		for hitman in range(K):
			if hitman_available(hitman, mask):
				mask_after = use_hitman(hitman, mask)
				for num_to_kill in range(1, N - already_killed + 1):
					dp[mask_after][num_to_kill + already_killed] = min(dp[mask_after][num_to_kill + already_killed], dp[mask][already_killed] + sum(cost[hitman][already_killed:already_killed + num_to_kill]))
print(min((dp[i][N] for i in range(MASK))))


import math
import os
import random
import re
import sys
(G, M) = [int(s) for s in input().split()]
costs = list()
cache = dict()
for i in range(M):
	costs.append([int(s) for s in input().split()])

def kill(gn, imercs):
	key = str(gn) + str(imercs)
	if key in cache:
		return cache[key]
	mercs = imercs[:]
	if gn == 0:
		return 0
	temp = list()
	for m in mercs:
		tempm = mercs[:]
		tempm.remove(m)
		if len(tempm) == 0:
			temp.append(sum(costs[m][:gn]))
		else:
			for c in range(gn - 1, -1, -1):
				temp.append(sum(costs[m][c:gn]) + kill(c, tempm))
	cache[key] = min(temp)
	return min(temp)
print(str(kill(G, [i for i in range(M)])))


import os
import sys
(N, K) = map(int, input().split())
cost = []
MASK = 2 << K
INF = 10 ** 8 - 1
for i in range(K):
	prices = list(map(int, input().split()))
	prices.reverse()
	cost.append(prices)
dp = []
for i in range(MASK):
	dp.append([INF] * (N + 1))
dp[0][0] = 0

def hitman_available(hitman, mask):
	return not 2 << hitman & mask

def use_hitman(hitman, mask):
	return mask | 2 << hitman
for already_killed in range(N):
	for mask in range(MASK):
		for hitman in range(K):
			if hitman_available(hitman, mask):
				mask_after = use_hitman(hitman, mask)
				for num_to_kill in range(1, N - already_killed + 1):
					dp[mask_after][num_to_kill + already_killed] = min(dp[mask_after][num_to_kill + already_killed], dp[mask][already_killed] + sum(cost[hitman][already_killed:already_killed + num_to_kill]))
print(min((dp[i][N] for i in range(MASK))))


(G, M) = [int(s) for s in input().split()]
costs = list()
cache = dict()
for i in range(M):
	costs.append([int(s) for s in input().split()])

def kill(gn, imercs):
	key = str(gn) + str(imercs)
	if key in cache:
		return cache[key]
	mercs = imercs[:]
	if gn == 0:
		return 0
	temp = list()
	for m in mercs:
		tempm = mercs[:]
		tempm.remove(m)
		if len(tempm) == 0:
			temp.append(sum(costs[m][:gn]))
		else:
			for c in range(gn - 1, -1, -1):
				temp.append(sum(costs[m][c:gn]) + kill(c, tempm))
	cache[key] = min(temp)
	return min(temp)
print(str(kill(G, [i for i in range(M)])))


import sys
(N, K) = map(int, sys.stdin.readline().split())
cost = []
MASK = 2 << K
INF = 10 ** 8 - 1
for i in range(K):
	prices = list(map(int, sys.stdin.readline().split()))
	prices.reverse()
	cost.append(prices)
dp = []
for i in range(MASK):
	dp.append([INF] * (N + 1))
dp[0][0] = 0

def hitman_available(hitman, mask):
	return not 2 << hitman & mask

def use_hitman(hitman, mask):
	return mask | 2 << hitman
for already_killed in range(N):
	for mask in range(MASK):
		for hitman in range(K):
			if hitman_available(hitman, mask):
				mask_after = use_hitman(hitman, mask)
				for num_to_kill in range(1, N - already_killed + 1):
					dp[mask_after][num_to_kill + already_killed] = min(dp[mask_after][num_to_kill + already_killed], dp[mask][already_killed] + sum(cost[hitman][already_killed:already_killed + num_to_kill]))
print(min((dp[i][N] for i in range(MASK))))


import os
import sys
(N, K) = map(int, input().split())
cost = []
MASK = 2 << K
INF = 10 ** 8 - 1
for i in range(K):
	prices = list(map(int, input().split()))
	prices.reverse()
	cost.append(prices)
dp = []
for i in range(MASK):
	dp.append([INF] * (N + 1))
dp[0][0] = 0

def hitman_available(hitman, mask):
	return not 2 << hitman & mask

def use_hitman(hitman, mask):
	return mask | 2 << hitman
for already_killed in range(N):
	for mask in range(MASK):
		for hitman in range(K):
			if hitman_available(hitman, mask):
				mask_after = use_hitman(hitman, mask)
				for num_to_kill in range(1, N - already_killed + 1):
					dp[mask_after][num_to_kill + already_killed] = min(dp[mask_after][num_to_kill + already_killed], dp[mask][already_killed] + sum(cost[hitman][already_killed:already_killed + num_to_kill]))
print(min((dp[i][N] for i in range(MASK))))


import os
import sys
(N, K) = map(int, input().split())
cost = []
MASK = 2 << K
INF = 10 ** 8 - 1
for i in range(K):
	prices = list(map(int, input().split()))
	prices.reverse()
	cost.append(prices)
dp = []
for i in range(MASK):
	dp.append([INF] * (N + 1))
dp[0][0] = 0

def hitman_available(hitman, mask):
	return not 2 << hitman & mask

def use_hitman(hitman, mask):
	return mask | 2 << hitman
for already_killed in range(N):
	for mask in range(MASK):
		for hitman in range(K):
			if hitman_available(hitman, mask):
				mask_after = use_hitman(hitman, mask)
				for num_to_kill in range(1, N - already_killed + 1):
					dp[mask_after][num_to_kill + already_killed] = min(dp[mask_after][num_to_kill + already_killed], dp[mask][already_killed] + sum(cost[hitman][already_killed:already_killed + num_to_kill]))
print(min((dp[i][N] for i in range(MASK))))


import os
import sys
(N, K) = map(int, input().split())
cost = []
MASK = 2 << K
INF = 10 ** 8 - 1
for i in range(K):
	prices = list(map(int, input().split()))
	prices.reverse()
	cost.append(prices)
dp = []
for i in range(MASK):
	dp.append([INF] * (N + 1))
dp[0][0] = 0

def hitman_available(hitman, mask):
	return not 2 << hitman & mask

def use_hitman(hitman, mask):
	return mask | 2 << hitman
for already_killed in range(N):
	for mask in range(MASK):
		for hitman in range(K):
			if hitman_available(hitman, mask):
				mask_after = use_hitman(hitman, mask)
				for num_to_kill in range(1, N - already_killed + 1):
					dp[mask_after][num_to_kill + already_killed] = min(dp[mask_after][num_to_kill + already_killed], dp[mask][already_killed] + sum(cost[hitman][already_killed:already_killed + num_to_kill]))
print(min((dp[i][N] for i in range(MASK))))


import os
import sys
(N, K) = map(int, input().split())
cost = []
MASK = 2 << K
INF = 10 ** 8 - 1
for i in range(K):
	prices = list(map(int, input().split()))
	prices.reverse()
	cost.append(prices)
dp = []
for i in range(MASK):
	dp.append([INF] * (N + 1))
dp[0][0] = 0

def hitman_available(hitman, mask):
	return not 2 << hitman & mask

def use_hitman(hitman, mask):
	return mask | 2 << hitman
for already_killed in range(N):
	for mask in range(MASK):
		for hitman in range(K):
			if hitman_available(hitman, mask):
				mask_after = use_hitman(hitman, mask)
				for num_to_kill in range(1, N - already_killed + 1):
					dp[mask_after][num_to_kill + already_killed] = min(dp[mask_after][num_to_kill + already_killed], dp[mask][already_killed] + sum(cost[hitman][already_killed:already_killed + num_to_kill]))
print(min((dp[i][N] for i in range(MASK))))


import os
import sys
(N, K) = map(int, input().split())
cost = []
MASK = 2 << K
INF = 10 ** 8 - 1
for i in range(K):
	prices = list(map(int, input().split()))
	prices.reverse()
	cost.append(prices)
dp = []
for i in range(MASK):
	dp.append([INF] * (N + 1))
dp[0][0] = 0

def hitman_available(hitman, mask):
	return not 2 << hitman & mask

def use_hitman(hitman, mask):
	return mask | 2 << hitman
for already_killed in range(N):
	for mask in range(MASK):
		for hitman in range(K):
			if hitman_available(hitman, mask):
				mask_after = use_hitman(hitman, mask)
				for num_to_kill in range(1, N - already_killed + 1):
					dp[mask_after][num_to_kill + already_killed] = min(dp[mask_after][num_to_kill + already_killed], dp[mask][already_killed] + sum(cost[hitman][already_killed:already_killed + num_to_kill]))
print(min((dp[i][N] for i in range(MASK))))


import os
import sys
(N, K) = map(int, input().split())
cost = []
MASK = 2 << K
INF = 10 ** 8 - 1
for i in range(K):
	prices = list(map(int, input().split()))
	prices.reverse()
	cost.append(prices)
dp = []
for i in range(MASK):
	dp.append([INF] * (N + 1))
dp[0][0] = 0

def hitman_available(hitman, mask):
	return not 2 << hitman & mask

def use_hitman(hitman, mask):
	return mask | 2 << hitman
for already_killed in range(N):
	for mask in range(MASK):
		for hitman in range(K):
			if hitman_available(hitman, mask):
				mask_after = use_hitman(hitman, mask)
				for num_to_kill in range(1, N - already_killed + 1):
					dp[mask_after][num_to_kill + already_killed] = min(dp[mask_after][num_to_kill + already_killed], dp[mask][already_killed] + sum(cost[hitman][already_killed:already_killed + num_to_kill]))
print(min((dp[i][N] for i in range(MASK))))


import os
import sys
(N, K) = map(int, input().split())
cost = []
MASK = 2 << K
INF = 10 ** 8 - 1
for i in range(K):
	prices = list(map(int, input().split()))
	prices.reverse()
	cost.append(prices)
dp = []
for i in range(MASK):
	dp.append([INF] * (N + 1))
dp[0][0] = 0

def hitman_available(hitman, mask):
	return not 2 << hitman & mask

def use_hitman(hitman, mask):
	return mask | 2 << hitman
for already_killed in range(N):
	for mask in range(MASK):
		for hitman in range(K):
			if hitman_available(hitman, mask):
				mask_after = use_hitman(hitman, mask)
				for num_to_kill in range(1, N - already_killed + 1):
					dp[mask_after][num_to_kill + already_killed] = min(dp[mask_after][num_to_kill + already_killed], dp[mask][already_killed] + sum(cost[hitman][already_killed:already_killed + num_to_kill]))
print(min((dp[i][N] for i in range(MASK))))


import os
import sys
(N, K) = map(int, input().split())
cost = []
MASK = 2 << K
INF = 10 ** 8 - 1
for i in range(K):
	prices = list(map(int, input().split()))
	prices.reverse()
	cost.append(prices)
dp = []
for i in range(MASK):
	dp.append([INF] * (N + 1))
dp[0][0] = 0

def hitman_available(hitman, mask):
	return not 2 << hitman & mask

def use_hitman(hitman, mask):
	return mask | 2 << hitman
for already_killed in range(N):
	for mask in range(MASK):
		for hitman in range(K):
			if hitman_available(hitman, mask):
				mask_after = use_hitman(hitman, mask)
				for num_to_kill in range(1, N - already_killed + 1):
					dp[mask_after][num_to_kill + already_killed] = min(dp[mask_after][num_to_kill + already_killed], dp[mask][already_killed] + sum(cost[hitman][already_killed:already_killed + num_to_kill]))
print(min((dp[i][N] for i in range(MASK))))


import os
import sys
(N, K) = map(int, input().split())
cost = []
MASK = 2 << K
INF = 10 ** 8 - 1
for i in range(K):
	prices = list(map(int, input().split()))
	prices.reverse()
	cost.append(prices)
dp = []
for i in range(MASK):
	dp.append([INF] * (N + 1))
dp[0][0] = 0

def hitman_available(hitman, mask):
	return not 2 << hitman & mask

def use_hitman(hitman, mask):
	return mask | 2 << hitman
for already_killed in range(N):
	for mask in range(MASK):
		for hitman in range(K):
			if hitman_available(hitman, mask):
				mask_after = use_hitman(hitman, mask)
				for num_to_kill in range(1, N - already_killed + 1):
					dp[mask_after][num_to_kill + already_killed] = min(dp[mask_after][num_to_kill + already_killed], dp[mask][already_killed] + sum(cost[hitman][already_killed:already_killed + num_to_kill]))
print(min((dp[i][N] for i in range(MASK))))


import os
import sys
(N, K) = map(int, input().split())
cost = []
MASK = 2 << K
INF = 10 ** 8 - 1
for i in range(K):
	prices = list(map(int, input().split()))
	prices.reverse()
	cost.append(prices)
dp = []
for i in range(MASK):
	dp.append([INF] * (N + 1))
dp[0][0] = 0

def hitman_available(hitman, mask):
	return not 2 << hitman & mask

def use_hitman(hitman, mask):
	return mask | 2 << hitman
for already_killed in range(N):
	for mask in range(MASK):
		for hitman in range(K):
			if hitman_available(hitman, mask):
				mask_after = use_hitman(hitman, mask)
				for num_to_kill in range(1, N - already_killed + 1):
					dp[mask_after][num_to_kill + already_killed] = min(dp[mask_after][num_to_kill + already_killed], dp[mask][already_killed] + sum(cost[hitman][already_killed:already_killed + num_to_kill]))
print(min((dp[i][N] for i in range(MASK))))


import os
import sys
(N, K) = map(int, input().split())
cost = []
MASK = 2 << K
INF = 10 ** 8 - 1
for i in range(K):
	prices = list(map(int, input().split()))
	prices.reverse()
	cost.append(prices)
dp = []
for i in range(MASK):
	dp.append([INF] * (N + 1))
dp[0][0] = 0

def hitman_available(hitman, mask):
	return not 2 << hitman & mask

def use_hitman(hitman, mask):
	return mask | 2 << hitman
for already_killed in range(N):
	for mask in range(MASK):
		for hitman in range(K):
			if hitman_available(hitman, mask):
				mask_after = use_hitman(hitman, mask)
				for num_to_kill in range(1, N - already_killed + 1):
					dp[mask_after][num_to_kill + already_killed] = min(dp[mask_after][num_to_kill + already_killed], dp[mask][already_killed] + sum(cost[hitman][already_killed:already_killed + num_to_kill]))
print(min((dp[i][N] for i in range(MASK))))


import os
import sys
(N, K) = map(int, input().split())
cost = []
MASK = 2 << K
INF = 10 ** 8 - 1
for i in range(K):
	prices = list(map(int, input().split()))
	prices.reverse()
	cost.append(prices)
dp = []
for i in range(MASK):
	dp.append([INF] * (N + 1))
dp[0][0] = 0

def hitman_available(hitman, mask):
	return not 2 << hitman & mask

def use_hitman(hitman, mask):
	return mask | 2 << hitman
for already_killed in range(N):
	for mask in range(MASK):
		for hitman in range(K):
			if hitman_available(hitman, mask):
				mask_after = use_hitman(hitman, mask)
				for num_to_kill in range(1, N - already_killed + 1):
					dp[mask_after][num_to_kill + already_killed] = min(dp[mask_after][num_to_kill + already_killed], dp[mask][already_killed] + sum(cost[hitman][already_killed:already_killed + num_to_kill]))
print(min((dp[i][N] for i in range(MASK))))


import math
import os
import random
import re
import sys
import os
import sys
(N, K) = map(int, input().split())
cost = []
MASK = 2 << K
INF = 10 ** 8 - 1
for i in range(K):
	prices = list(map(int, input().split()))
	prices.reverse()
	cost.append(prices)
dp = []
for i in range(MASK):
	dp.append([INF] * (N + 1))
dp[0][0] = 0

def hitman_available(hitman, mask):
	return not 2 << hitman & mask

def use_hitman(hitman, mask):
	return mask | 2 << hitman
for already_killed in range(N):
	for mask in range(MASK):
		for hitman in range(K):
			if hitman_available(hitman, mask):
				mask_after = use_hitman(hitman, mask)
				for num_to_kill in range(1, N - already_killed + 1):
					dp[mask_after][num_to_kill + already_killed] = min(dp[mask_after][num_to_kill + already_killed], dp[mask][already_killed] + sum(cost[hitman][already_killed:already_killed + num_to_kill]))
print(min((dp[i][N] for i in range(MASK))))


(G, M) = [int(s) for s in input().split()]
costs = list()
cache = dict()
for i in range(M):
	costs.append([int(s) for s in input().split()])

def kill(gn, imercs):
	key = str(gn) + str(imercs)
	if key in cache:
		return cache[key]
	mercs = imercs[:]
	if gn == 0:
		return 0
	temp = list()
	for m in mercs:
		tempm = mercs[:]
		tempm.remove(m)
		if len(tempm) == 0:
			temp.append(sum(costs[m][:gn]))
		else:
			for c in range(gn - 1, -1, -1):
				temp.append(sum(costs[m][c:gn]) + kill(c, tempm))
	cache[key] = min(temp)
	return min(temp)
print(str(kill(G, [i for i in range(M)])))


import os
import sys
(N, K) = map(int, input().split())
cost = []
MASK = 2 << K
INF = 10 ** 8 - 1
for i in range(K):
	prices = list(map(int, input().split()))
	prices.reverse()
	cost.append(prices)
dp = []
for i in range(MASK):
	dp.append([INF] * (N + 1))
dp[0][0] = 0

def hitman_available(hitman, mask):
	return not 2 << hitman & mask

def use_hitman(hitman, mask):
	return mask | 2 << hitman
for already_killed in range(N):
	for mask in range(MASK):
		for hitman in range(K):
			if hitman_available(hitman, mask):
				mask_after = use_hitman(hitman, mask)
				for num_to_kill in range(1, N - already_killed + 1):
					dp[mask_after][num_to_kill + already_killed] = min(dp[mask_after][num_to_kill + already_killed], dp[mask][already_killed] + sum(cost[hitman][already_killed:already_killed + num_to_kill]))
print(min((dp[i][N] for i in range(MASK))))


import os
import sys
(N, K) = map(int, input().split())
cost = []
MASK = 2 << K
INF = 10 ** 8 - 1
for i in range(K):
	prices = list(map(int, input().split()))
	prices.reverse()
	cost.append(prices)
dp = []
for i in range(MASK):
	dp.append([INF] * (N + 1))
dp[0][0] = 0

def hitman_available(hitman, mask):
	return not 2 << hitman & mask

def use_hitman(hitman, mask):
	return mask | 2 << hitman
for already_killed in range(N):
	for mask in range(MASK):
		for hitman in range(K):
			if hitman_available(hitman, mask):
				mask_after = use_hitman(hitman, mask)
				for num_to_kill in range(1, N - already_killed + 1):
					dp[mask_after][num_to_kill + already_killed] = min(dp[mask_after][num_to_kill + already_killed], dp[mask][already_killed] + sum(cost[hitman][already_killed:already_killed + num_to_kill]))
print(min((dp[i][N] for i in range(MASK))))


import os
import sys
(N, K) = map(int, input().split())
cost = []
MASK = 2 << K
INF = 10 ** 8 - 1
for i in range(K):
	prices = list(map(int, input().split()))
	prices.reverse()
	cost.append(prices)
dp = []
for i in range(MASK):
	dp.append([INF] * (N + 1))
dp[0][0] = 0

def hitman_available(hitman, mask):
	return not 2 << hitman & mask

def use_hitman(hitman, mask):
	return mask | 2 << hitman
for already_killed in range(N):
	for mask in range(MASK):
		for hitman in range(K):
			if hitman_available(hitman, mask):
				mask_after = use_hitman(hitman, mask)
				for num_to_kill in range(1, N - already_killed + 1):
					dp[mask_after][num_to_kill + already_killed] = min(dp[mask_after][num_to_kill + already_killed], dp[mask][already_killed] + sum(cost[hitman][already_killed:already_killed + num_to_kill]))
print(min((dp[i][N] for i in range(MASK))))


import os
import sys
(N, K) = map(int, input().split())
cost = []
MASK = 2 << K
INF = 10 ** 8 - 1
for i in range(K):
	prices = list(map(int, input().split()))
	prices.reverse()
	cost.append(prices)
dp = []
for i in range(MASK):
	dp.append([INF] * (N + 1))
dp[0][0] = 0

def hitman_available(hitman, mask):
	return not 2 << hitman & mask

def use_hitman(hitman, mask):
	return mask | 2 << hitman
for already_killed in range(N):
	for mask in range(MASK):
		for hitman in range(K):
			if hitman_available(hitman, mask):
				mask_after = use_hitman(hitman, mask)
				for num_to_kill in range(1, N - already_killed + 1):
					dp[mask_after][num_to_kill + already_killed] = min(dp[mask_after][num_to_kill + already_killed], dp[mask][already_killed] + sum(cost[hitman][already_killed:already_killed + num_to_kill]))
print(min((dp[i][N] for i in range(MASK))))


import os
import sys
(N, K) = map(int, input().split())
cost = []
MASK = 2 << K
INF = 10 ** 8 - 1
for i in range(K):
	prices = list(map(int, input().split()))
	prices.reverse()
	cost.append(prices)
dp = []
for i in range(MASK):
	dp.append([INF] * (N + 1))
dp[0][0] = 0

def hitman_available(hitman, mask):
	return not 2 << hitman & mask

def use_hitman(hitman, mask):
	return mask | 2 << hitman
for already_killed in range(N):
	for mask in range(MASK):
		for hitman in range(K):
			if hitman_available(hitman, mask):
				mask_after = use_hitman(hitman, mask)
				for num_to_kill in range(1, N - already_killed + 1):
					dp[mask_after][num_to_kill + already_killed] = min(dp[mask_after][num_to_kill + already_killed], dp[mask][already_killed] + sum(cost[hitman][already_killed:already_killed + num_to_kill]))
print(min((dp[i][N] for i in range(MASK))))


import os
import sys
(N, K) = map(int, input().split())
cost = []
MASK = 2 << K
INF = 10 ** 8 - 1
for i in range(K):
	prices = list(map(int, input().split()))
	prices.reverse()
	cost.append(prices)
dp = []
for i in range(MASK):
	dp.append([INF] * (N + 1))
dp[0][0] = 0

def hitman_available(hitman, mask):
	return not 2 << hitman & mask

def use_hitman(hitman, mask):
	return mask | 2 << hitman
for already_killed in range(N):
	for mask in range(MASK):
		for hitman in range(K):
			if hitman_available(hitman, mask):
				mask_after = use_hitman(hitman, mask)
				for num_to_kill in range(1, N - already_killed + 1):
					dp[mask_after][num_to_kill + already_killed] = min(dp[mask_after][num_to_kill + already_killed], dp[mask][already_killed] + sum(cost[hitman][already_killed:already_killed + num_to_kill]))
print(min((dp[i][N] for i in range(MASK))))


import os
import sys
(N, K) = map(int, input().split())
cost = []
MASK = 2 << K
INF = 10 ** 8 - 1
for i in range(K):
	prices = list(map(int, input().split()))
	prices.reverse()
	cost.append(prices)
dp = []
for i in range(MASK):
	dp.append([INF] * (N + 1))
dp[0][0] = 0

def hitman_available(hitman, mask):
	return not 2 << hitman & mask

def use_hitman(hitman, mask):
	return mask | 2 << hitman
for already_killed in range(N):
	for mask in range(MASK):
		for hitman in range(K):
			if hitman_available(hitman, mask):
				mask_after = use_hitman(hitman, mask)
				for num_to_kill in range(1, N - already_killed + 1):
					dp[mask_after][num_to_kill + already_killed] = min(dp[mask_after][num_to_kill + already_killed], dp[mask][already_killed] + sum(cost[hitman][already_killed:already_killed + num_to_kill]))
print(min((dp[i][N] for i in range(MASK))))


import os
import sys
(N, K) = map(int, input().split())
cost = []
MASK = 2 << K
INF = 10 ** 8 - 1
for i in range(K):
	prices = list(map(int, input().split()))
	prices.reverse()
	cost.append(prices)
dp = []
for i in range(MASK):
	dp.append([INF] * (N + 1))
dp[0][0] = 0

def hitman_available(hitman, mask):
	return not 2 << hitman & mask

def use_hitman(hitman, mask):
	return mask | 2 << hitman
for already_killed in range(N):
	for mask in range(MASK):
		for hitman in range(K):
			if hitman_available(hitman, mask):
				mask_after = use_hitman(hitman, mask)
				for num_to_kill in range(1, N - already_killed + 1):
					dp[mask_after][num_to_kill + already_killed] = min(dp[mask_after][num_to_kill + already_killed], dp[mask][already_killed] + sum(cost[hitman][already_killed:already_killed + num_to_kill]))
print(min((dp[i][N] for i in range(MASK))))


import os
import sys
(N, K) = map(int, input().split())
cost = []
MASK = 2 << K
INF = 10 ** 8 - 1
for i in range(K):
	prices = list(map(int, input().split()))
	prices.reverse()
	cost.append(prices)
dp = []
for i in range(MASK):
	dp.append([INF] * (N + 1))
dp[0][0] = 0

def hitman_available(hitman, mask):
	return not 2 << hitman & mask

def use_hitman(hitman, mask):
	return mask | 2 << hitman
for already_killed in range(N):
	for mask in range(MASK):
		for hitman in range(K):
			if hitman_available(hitman, mask):
				mask_after = use_hitman(hitman, mask)
				for num_to_kill in range(1, N - already_killed + 1):
					dp[mask_after][num_to_kill + already_killed] = min(dp[mask_after][num_to_kill + already_killed], dp[mask][already_killed] + sum(cost[hitman][already_killed:already_killed + num_to_kill]))
print(min((dp[i][N] for i in range(MASK))))


import os
import sys
(N, K) = map(int, input().split())
cost = []
MASK = 2 << K
INF = 10 ** 8 - 1
for i in range(K):
	prices = list(map(int, input().split()))
	prices.reverse()
	cost.append(prices)
dp = []
for i in range(MASK):
	dp.append([INF] * (N + 1))
dp[0][0] = 0

def hitman_available(hitman, mask):
	return not 2 << hitman & mask

def use_hitman(hitman, mask):
	return mask | 2 << hitman
for already_killed in range(N):
	for mask in range(MASK):
		for hitman in range(K):
			if hitman_available(hitman, mask):
				mask_after = use_hitman(hitman, mask)
				for num_to_kill in range(1, N - already_killed + 1):
					dp[mask_after][num_to_kill + already_killed] = min(dp[mask_after][num_to_kill + already_killed], dp[mask][already_killed] + sum(cost[hitman][already_killed:already_killed + num_to_kill]))
print(min((dp[i][N] for i in range(MASK))))


import os
import sys
(N, K) = map(int, input().split())
cost = []
MASK = 2 << K
INF = 10 ** 8 - 1
for i in range(K):
	prices = list(map(int, input().split()))
	prices.reverse()
	cost.append(prices)
dp = []
for i in range(MASK):
	dp.append([INF] * (N + 1))
dp[0][0] = 0

def hitman_available(hitman, mask):
	return not 2 << hitman & mask

def use_hitman(hitman, mask):
	return mask | 2 << hitman
for already_killed in range(N):
	for mask in range(MASK):
		for hitman in range(K):
			if hitman_available(hitman, mask):
				mask_after = use_hitman(hitman, mask)
				for num_to_kill in range(1, N - already_killed + 1):
					dp[mask_after][num_to_kill + already_killed] = min(dp[mask_after][num_to_kill + already_killed], dp[mask][already_killed] + sum(cost[hitman][already_killed:already_killed + num_to_kill]))
print(min((dp[i][N] for i in range(MASK))))


import os
import sys
(N, K) = map(int, input().split())
cost = []
MASK = 2 << K
INF = 10 ** 8 - 1
for i in range(K):
	prices = list(map(int, input().split()))
	prices.reverse()
	cost.append(prices)
dp = []
for i in range(MASK):
	dp.append([INF] * (N + 1))
dp[0][0] = 0

def hitman_available(hitman, mask):
	return not 2 << hitman & mask

def use_hitman(hitman, mask):
	return mask | 2 << hitman
for already_killed in range(N):
	for mask in range(MASK):
		for hitman in range(K):
			if hitman_available(hitman, mask):
				mask_after = use_hitman(hitman, mask)
				for num_to_kill in range(1, N - already_killed + 1):
					dp[mask_after][num_to_kill + already_killed] = min(dp[mask_after][num_to_kill + already_killed], dp[mask][already_killed] + sum(cost[hitman][already_killed:already_killed + num_to_kill]))
print(min((dp[i][N] for i in range(MASK))))


(G, M) = [int(s) for s in input().split()]
costs = list()
cache = dict()
for i in range(M):
	costs.append([int(s) for s in input().split()])

def kill(gn, imercs):
	key = str(gn) + str(imercs)
	if key in cache:
		return cache[key]
	mercs = imercs[:]
	if gn == 0:
		return 0
	temp = list()
	for m in mercs:
		tempm = mercs[:]
		tempm.remove(m)
		if len(tempm) == 0:
			temp.append(sum(costs[m][:gn]))
		else:
			for c in range(gn - 1, -1, -1):
				temp.append(sum(costs[m][c:gn]) + kill(c, tempm))
	cache[key] = min(temp)
	return min(temp)
print(str(kill(G, [i for i in range(M)])))


import os
import sys
(N, K) = map(int, input().split())
cost = []
MASK = 2 << K
INF = 10 ** 8 - 1
for i in range(K):
	prices = list(map(int, input().split()))
	prices.reverse()
	cost.append(prices)
dp = []
for i in range(MASK):
	dp.append([INF] * (N + 1))
dp[0][0] = 0

def hitman_available(hitman, mask):
	return not 2 << hitman & mask

def use_hitman(hitman, mask):
	return mask | 2 << hitman
for already_killed in range(N):
	for mask in range(MASK):
		for hitman in range(K):
			if hitman_available(hitman, mask):
				mask_after = use_hitman(hitman, mask)
				for num_to_kill in range(1, N - already_killed + 1):
					dp[mask_after][num_to_kill + already_killed] = min(dp[mask_after][num_to_kill + already_killed], dp[mask][already_killed] + sum(cost[hitman][already_killed:already_killed + num_to_kill]))
print(min((dp[i][N] for i in range(MASK))))


import os
import sys
(N, K) = map(int, input().split())
cost = []
MASK = 2 << K
INF = 10 ** 8 - 1
for i in range(K):
	prices = list(map(int, input().split()))
	prices.reverse()
	cost.append(prices)
dp = []
for i in range(MASK):
	dp.append([INF] * (N + 1))
dp[0][0] = 0

def hitman_available(hitman, mask):
	return not 2 << hitman & mask

def use_hitman(hitman, mask):
	return mask | 2 << hitman
for already_killed in range(N):
	for mask in range(MASK):
		for hitman in range(K):
			if hitman_available(hitman, mask):
				mask_after = use_hitman(hitman, mask)
				for num_to_kill in range(1, N - already_killed + 1):
					dp[mask_after][num_to_kill + already_killed] = min(dp[mask_after][num_to_kill + already_killed], dp[mask][already_killed] + sum(cost[hitman][already_killed:already_killed + num_to_kill]))
print(min((dp[i][N] for i in range(MASK))))


import os
import sys
(N, K) = map(int, input().split())
cost = []
MASK = 2 << K
INF = 10 ** 8 - 1
for i in range(K):
	prices = list(map(int, input().split()))
	prices.reverse()
	cost.append(prices)
dp = []
for i in range(MASK):
	dp.append([INF] * (N + 1))
dp[0][0] = 0

def hitman_available(hitman, mask):
	return not 2 << hitman & mask

def use_hitman(hitman, mask):
	return mask | 2 << hitman
for already_killed in range(N):
	for mask in range(MASK):
		for hitman in range(K):
			if hitman_available(hitman, mask):
				mask_after = use_hitman(hitman, mask)
				for num_to_kill in range(1, N - already_killed + 1):
					dp[mask_after][num_to_kill + already_killed] = min(dp[mask_after][num_to_kill + already_killed], dp[mask][already_killed] + sum(cost[hitman][already_killed:already_killed + num_to_kill]))
print(min((dp[i][N] for i in range(MASK))))


import os
import sys
(N, K) = map(int, input().split())
cost = []
MASK = 2 << K
INF = 10 ** 8 - 1
for i in range(K):
	prices = list(map(int, input().split()))
	prices.reverse()
	cost.append(prices)
dp = []
for i in range(MASK):
	dp.append([INF] * (N + 1))
dp[0][0] = 0

def hitman_available(hitman, mask):
	return not 2 << hitman & mask

def use_hitman(hitman, mask):
	return mask | 2 << hitman
for already_killed in range(N):
	for mask in range(MASK):
		for hitman in range(K):
			if hitman_available(hitman, mask):
				mask_after = use_hitman(hitman, mask)
				for num_to_kill in range(1, N - already_killed + 1):
					dp[mask_after][num_to_kill + already_killed] = min(dp[mask_after][num_to_kill + already_killed], dp[mask][already_killed] + sum(cost[hitman][already_killed:already_killed + num_to_kill]))
print(min((dp[i][N] for i in range(MASK))))


import os
import sys
(N, K) = map(int, input().split())
cost = []
MASK = 2 << K
INF = 10 ** 8 - 1
for i in range(K):
	w = list(map(int, input().split()))
	w.reverse()
	cost.append(w)
q = []
for i in range(MASK):
	q.append([INF] * (N + 1))
q[0][0] = 0

def hitman_available(s, mask):
	return not 2 << s & mask

def use_hitman(s, mask):
	return mask | 2 << s
for already_killed in range(N):
	for mask in range(MASK):
		for s in range(K):
			if hitman_available(s, mask):
				mask_after = use_hitman(s, mask)
				for num_to_kill in range(1, N - already_killed + 1):
					q[mask_after][num_to_kill + already_killed] = min(q[mask_after][num_to_kill + already_killed], q[mask][already_killed] + sum(cost[s][already_killed:already_killed + num_to_kill]))
print(min((q[i][N] for i in range(MASK))))


import os
import sys
(H, L) = map(int, input().split())
cost = []
MASK = 2 << L
INF = 10 ** 8 - 1
for i in range(L):
	prices = list(map(int, input().split()))
	prices.reverse()
	cost.append(prices)
dp = []
for i in range(MASK):
	dp.append([INF] * (H + 1))
dp[0][0] = 0

def hitman_available(hitman, mask):
	return not 2 << hitman & mask

def use_hitman(hitman, mask):
	return mask | 2 << hitman
for already_killed in range(H):
	for mask in range(MASK):
		for hitman in range(L):
			if hitman_available(hitman, mask):
				mask_after = use_hitman(hitman, mask)
				for num_to_kill in range(1, H - already_killed + 1):
					dp[mask_after][num_to_kill + already_killed] = min(dp[mask_after][num_to_kill + already_killed], dp[mask][already_killed] + sum(cost[hitman][already_killed:already_killed + num_to_kill]))
print(min((dp[i][H] for i in range(MASK))))


import os
import sys
(P, K) = map(int, input().split())
cost = []
MASK = 2 << K
INF = 10 ** 8 - 1
for i in range(K):
	prices = list(map(int, input().split()))
	prices.reverse()
	cost.append(prices)
dp = []
for i in range(MASK):
	dp.append([INF] * (P + 1))
dp[0][0] = 0

def hitman_available(hitman, mask):
	return not 2 << hitman & mask

def use_hitman(hitman, mask):
	return mask | 2 << hitman
for already_killed in range(P):
	for mask in range(MASK):
		for hitman in range(K):
			if hitman_available(hitman, mask):
				mask_after = use_hitman(hitman, mask)
				for num_to_kill in range(1, P - already_killed + 1):
					dp[mask_after][num_to_kill + already_killed] = min(dp[mask_after][num_to_kill + already_killed], dp[mask][already_killed] + sum(cost[hitman][already_killed:already_killed + num_to_kill]))
print(min((dp[i][P] for i in range(MASK))))


import os
import sys
(N, K) = map(int, input().split())
cost = []
MASK = 2 << K
INF = 10 ** 8 - 1
for i in range(K):
	prices = list(map(int, input().split()))
	prices.reverse()
	cost.append(prices)
dp = []
for i in range(MASK):
	dp.append([INF] * (N + 1))
dp[0][0] = 0

def hitman_available(hitman, mask):
	return not 2 << hitman & mask

def use_hitman(hitman, mask):
	return mask | 2 << hitman
for already_killed in range(N):
	for mask in range(MASK):
		for hitman in range(K):
			if hitman_available(hitman, mask):
				mask_after = use_hitman(hitman, mask)
				for num_to_kill in range(1, N - already_killed + 1):
					dp[mask_after][num_to_kill + already_killed] = min(dp[mask_after][num_to_kill + already_killed], dp[mask][already_killed] + sum(cost[hitman][already_killed:already_killed + num_to_kill]))
print(min((dp[i][N] for i in range(MASK))))


import os
import sys
(N, K) = map(int, input().split())
cost = []
MASK = 2 << K
INF = 10 ** 8 - 1
for i in range(K):
	prices = list(map(int, input().split()))
	prices.reverse()
	cost.append(prices)
dp = []
for i in range(MASK):
	dp.append([INF] * (N + 1))
dp[0][0] = 0

def hitman_available(hitman, mask):
	return not 2 << hitman & mask

def use_hitman(hitman, mask):
	return mask | 2 << hitman
for already_killed in range(N):
	for mask in range(MASK):
		for hitman in range(K):
			if hitman_available(hitman, mask):
				mask_after = use_hitman(hitman, mask)
				for num_to_kill in range(1, N - already_killed + 1):
					dp[mask_after][num_to_kill + already_killed] = min(dp[mask_after][num_to_kill + already_killed], dp[mask][already_killed] + sum(cost[hitman][already_killed:already_killed + num_to_kill]))
print(min((dp[i][N] for i in range(MASK))))


import os
import sys
(N, K) = map(int, input().split())
cost = []
MASK = 2 << K
INF = 10 ** 8 - 1
for i in range(K):
	prices = list(map(int, input().split()))
	prices.reverse()
	cost.append(prices)
dp = []
for i in range(MASK):
	dp.append([INF] * (N + 1))
dp[0][0] = 0

def hitman_available(hitman, mask):
	return not 2 << hitman & mask

def use_hitman(hitman, mask):
	return mask | 2 << hitman
for already_killed in range(N):
	for mask in range(MASK):
		for hitman in range(K):
			if hitman_available(hitman, mask):
				mask_after = use_hitman(hitman, mask)
				for num_to_kill in range(1, N - already_killed + 1):
					dp[mask_after][num_to_kill + already_killed] = min(dp[mask_after][num_to_kill + already_killed], dp[mask][already_killed] + sum(cost[hitman][already_killed:already_killed + num_to_kill]))
print(min((dp[i][N] for i in range(MASK))))


def bits_free(x, K):
	res = []
	for i in range(K):
		if x % 2 == 0:
			res.append(i)
		x //= 2
	return res
(N, K) = tuple((int(s) for s in input().strip().split()))
costs = []
for i in range(K):
	costs1 = [int(s) for s in input().strip().split()]
	costs.append(costs1)
dpmat = [[[1000000 for i in range(2 ** K)] for j in range(K)] for k in range(N)]
for mer in range(K):
	dpmat[0][mer][1 << mer] = costs[mer][0]
for gan in range(1, N):
	for lastmer in range(K):
		for mask in range(2 ** K):
			if dpmat[gan - 1][lastmer][mask] >= 1000000:
				continue
			dpmat[gan][lastmer][mask] = min(dpmat[gan][lastmer][mask], dpmat[gan - 1][lastmer][mask] + costs[lastmer][gan])
			for newmer in bits_free(mask, K):
				newmask = mask | 1 << newmer
				dpmat[gan][newmer][newmask] = min(dpmat[gan][newmer][newmask], dpmat[gan - 1][lastmer][mask] + costs[newmer][gan])
best = 1000000
for lastmer in range(K):
	for mask in range(2 ** K):
		if dpmat[N - 1][lastmer][mask] < 0:
			continue
		best = min(best, dpmat[N - 1][lastmer][mask])
print(best)


import os
import sys
(N, K) = map(int, input().split())
cost = []
MASK = 2 << K
INF = 10 ** 8 - 1
for i in range(K):
	prices = list(map(int, input().split()))
	prices.reverse()
	cost.append(prices)
dp = []
for i in range(MASK):
	dp.append([INF] * (N + 1))
dp[0][0] = 0

def hitman_available(hitman, mask):
	return not 2 << hitman & mask

def use_hitman(hitman, mask):
	return mask | 2 << hitman
for already_killed in range(N):
	for mask in range(MASK):
		for hitman in range(K):
			if hitman_available(hitman, mask):
				mask_after = use_hitman(hitman, mask)
				for num_to_kill in range(1, N - already_killed + 1):
					dp[mask_after][num_to_kill + already_killed] = min(dp[mask_after][num_to_kill + already_killed], dp[mask][already_killed] + sum(cost[hitman][already_killed:already_killed + num_to_kill]))
print(min((dp[i][N] for i in range(MASK))))


import os
import sys
(N, K) = map(int, input().split())
cost = []
MASK = 2 << K
INF = 10 ** 8 - 1
for i in range(K):
	prices = list(map(int, input().split()))
	prices.reverse()
	cost.append(prices)
dp = []
for i in range(MASK):
	dp.append([INF] * (N + 1))
dp[0][0] = 0

def hitman_available(hitman, mask):
	return not 2 << hitman & mask

def use_hitman(hitman, mask):
	return mask | 2 << hitman
for already_killed in range(N):
	for mask in range(MASK):
		for hitman in range(K):
			if hitman_available(hitman, mask):
				mask_after = use_hitman(hitman, mask)
				for num_to_kill in range(1, N - already_killed + 1):
					dp[mask_after][num_to_kill + already_killed] = min(dp[mask_after][num_to_kill + already_killed], dp[mask][already_killed] + sum(cost[hitman][already_killed:already_killed + num_to_kill]))
print(min((dp[i][N] for i in range(MASK))))


def bits_free(x, K):
	res = []
	for i in range(K):
		if x % 2 == 0:
			res.append(i)
		x //= 2
	return res
(N, K) = tuple((int(s) for s in input().strip().split()))
costs = []
for i in range(K):
	costs1 = [int(s) for s in input().strip().split()]
	costs.append(costs1)
dpmat = [[[1000000 for i in range(2 ** K)] for j in range(K)] for k in range(N)]
for mer in range(K):
	dpmat[0][mer][1 << mer] = costs[mer][0]
for gan in range(1, N):
	for lastmer in range(K):
		for mask in range(2 ** K):
			if dpmat[gan - 1][lastmer][mask] >= 1000000:
				continue
			dpmat[gan][lastmer][mask] = min(dpmat[gan][lastmer][mask], dpmat[gan - 1][lastmer][mask] + costs[lastmer][gan])
			for newmer in bits_free(mask, K):
				newmask = mask | 1 << newmer
				dpmat[gan][newmer][newmask] = min(dpmat[gan][newmer][newmask], dpmat[gan - 1][lastmer][mask] + costs[newmer][gan])
best = 1000000
for lastmer in range(K):
	for mask in range(2 ** K):
		if dpmat[N - 1][lastmer][mask] < 0:
			continue
		best = min(best, dpmat[N - 1][lastmer][mask])
print(best)


def bits_free(x, K):
	res = []
	for i in range(K):
		if x % 2 == 0:
			res.append(i)
		x //= 2
	return res
(N, K) = tuple((int(s) for s in input().strip().split()))
costs = []
for i in range(K):
	costs1 = [int(s) for s in input().strip().split()]
	costs.append(costs1)
dpmat = [[[1000000 for i in range(2 ** K)] for j in range(K)] for k in range(N)]
for mer in range(K):
	dpmat[0][mer][1 << mer] = costs[mer][0]
for gan in range(1, N):
	for lastmer in range(K):
		for mask in range(2 ** K):
			if dpmat[gan - 1][lastmer][mask] >= 1000000:
				continue
			dpmat[gan][lastmer][mask] = min(dpmat[gan][lastmer][mask], dpmat[gan - 1][lastmer][mask] + costs[lastmer][gan])
			for newmer in bits_free(mask, K):
				newmask = mask | 1 << newmer
				dpmat[gan][newmer][newmask] = min(dpmat[gan][newmer][newmask], dpmat[gan - 1][lastmer][mask] + costs[newmer][gan])
best = 1000000
for lastmer in range(K):
	for mask in range(2 ** K):
		if dpmat[N - 1][lastmer][mask] < 0:
			continue
		best = min(best, dpmat[N - 1][lastmer][mask])
print(best)


def bits_free(x, K):
	res = []
	for i in range(K):
		if x % 2 == 0:
			res.append(i)
		x //= 2
	return res
(N, K) = tuple((int(s) for s in input().strip().split()))
costs = []
for i in range(K):
	costs1 = [int(s) for s in input().strip().split()]
	costs.append(costs1)
dpmat = [[[1000000 for i in range(2 ** K)] for j in range(K)] for k in range(N)]
for mer in range(K):
	dpmat[0][mer][1 << mer] = costs[mer][0]
for gan in range(1, N):
	for lastmer in range(K):
		for mask in range(2 ** K):
			if dpmat[gan - 1][lastmer][mask] >= 1000000:
				continue
			dpmat[gan][lastmer][mask] = min(dpmat[gan][lastmer][mask], dpmat[gan - 1][lastmer][mask] + costs[lastmer][gan])
			for newmer in bits_free(mask, K):
				newmask = mask | 1 << newmer
				dpmat[gan][newmer][newmask] = min(dpmat[gan][newmer][newmask], dpmat[gan - 1][lastmer][mask] + costs[newmer][gan])
best = 1000000
for lastmer in range(K):
	for mask in range(2 ** K):
		if dpmat[N - 1][lastmer][mask] < 0:
			continue
		best = min(best, dpmat[N - 1][lastmer][mask])
print(best)


def bits_free(x, K):
	res = []
	for i in range(K):
		if x % 2 == 0:
			res.append(i)
		x //= 2
	return res
(N, K) = tuple((int(s) for s in input().strip().split()))
costs = []
for i in range(K):
	costs1 = [int(s) for s in input().strip().split()]
	costs.append(costs1)
dpmat = [[[1000000 for i in range(2 ** K)] for j in range(K)] for k in range(N)]
for mer in range(K):
	dpmat[0][mer][1 << mer] = costs[mer][0]
for gan in range(1, N):
	for lastmer in range(K):
		for mask in range(2 ** K):
			if dpmat[gan - 1][lastmer][mask] >= 1000000:
				continue
			dpmat[gan][lastmer][mask] = min(dpmat[gan][lastmer][mask], dpmat[gan - 1][lastmer][mask] + costs[lastmer][gan])
			for newmer in bits_free(mask, K):
				newmask = mask | 1 << newmer
				dpmat[gan][newmer][newmask] = min(dpmat[gan][newmer][newmask], dpmat[gan - 1][lastmer][mask] + costs[newmer][gan])
best = 1000000
for lastmer in range(K):
	for mask in range(2 ** K):
		if dpmat[N - 1][lastmer][mask] < 0:
			continue
		best = min(best, dpmat[N - 1][lastmer][mask])
print(best)


import os
import sys
(N, K) = map(int, input().split())
cost = []
MASK = 2 << K
INF = 10 ** 8 - 1
for i in range(K):
	prices = list(map(int, input().split()))
	prices.reverse()
	cost.append(prices)
dp = []
for i in range(MASK):
	dp.append([INF] * (N + 1))
dp[0][0] = 0

def hitman_available(hitman, mask):
	return not 2 << hitman & mask

def use_hitman(hitman, mask):
	return mask | 2 << hitman
for already_killed in range(N):
	for mask in range(MASK):
		for hitman in range(K):
			if hitman_available(hitman, mask):
				mask_after = use_hitman(hitman, mask)
				for num_to_kill in range(1, N - already_killed + 1):
					dp[mask_after][num_to_kill + already_killed] = min(dp[mask_after][num_to_kill + already_killed], dp[mask][already_killed] + sum(cost[hitman][already_killed:already_killed + num_to_kill]))
print(min((dp[i][N] for i in range(MASK))))


import os
import sys
(N, K) = map(int, input().split())
cost = []
MASK = 2 << K
INF = 10 ** 8 - 1
for i in range(K):
	prices = list(map(int, input().split()))
	prices.reverse()
	cost.append(prices)
dp = []
for i in range(MASK):
	dp.append([INF] * (N + 1))
dp[0][0] = 0

def hitman_available(hitman, mask):
	return not 2 << hitman & mask

def use_hitman(hitman, mask):
	return mask | 2 << hitman
for already_killed in range(N):
	for mask in range(MASK):
		for hitman in range(K):
			if hitman_available(hitman, mask):
				mask_after = use_hitman(hitman, mask)
				for num_to_kill in range(1, N - already_killed + 1):
					dp[mask_after][num_to_kill + already_killed] = min(dp[mask_after][num_to_kill + already_killed], dp[mask][already_killed] + sum(cost[hitman][already_killed:already_killed + num_to_kill]))
print(min((dp[i][N] for i in range(MASK))))


import os
import sys
(N, K) = map(int, input().split())
cost = []
MASK = 2 << K
INF = 10 ** 8 - 1
for i in range(K):
	prices = list(map(int, input().split()))
	prices.reverse()
	cost.append(prices)
dp = []
for i in range(MASK):
	dp.append([INF] * (N + 1))
dp[0][0] = 0

def hitman_available(hitman, mask):
	return not 2 << hitman & mask

def use_hitman(hitman, mask):
	return mask | 2 << hitman
for already_killed in range(N):
	for mask in range(MASK):
		for hitman in range(K):
			if hitman_available(hitman, mask):
				mask_after = use_hitman(hitman, mask)
				for num_to_kill in range(1, N - already_killed + 1):
					dp[mask_after][num_to_kill + already_killed] = min(dp[mask_after][num_to_kill + already_killed], dp[mask][already_killed] + sum(cost[hitman][already_killed:already_killed + num_to_kill]))
print(min((dp[i][N] for i in range(MASK))))


import os
import sys
(N, K) = map(int, input().split())
cost = []
MASK = 2 << K
INF = 10 ** 8 - 1
for i in range(K):
	prices = list(map(int, input().split()))
	prices.reverse()
	cost.append(prices)
dp = []
for i in range(MASK):
	dp.append([INF] * (N + 1))
dp[0][0] = 0

def hitman_available(hitman, mask):
	return not 2 << hitman & mask

def use_hitman(hitman, mask):
	return mask | 2 << hitman
for already_killed in range(N):
	for mask in range(MASK):
		for hitman in range(K):
			if hitman_available(hitman, mask):
				mask_after = use_hitman(hitman, mask)
				for num_to_kill in range(1, N - already_killed + 1):
					dp[mask_after][num_to_kill + already_killed] = min(dp[mask_after][num_to_kill + already_killed], dp[mask][already_killed] + sum(cost[hitman][already_killed:already_killed + num_to_kill]))
print(min((dp[i][N] for i in range(MASK))))


import os
import sys
(N, K) = map(int, input().split())
cost = []
MASK = 2 << K
INF = 10 ** 8 - 1
for i in range(K):
	prices = list(map(int, input().split()))
	prices.reverse()
	cost.append(prices)
dp = []
for i in range(MASK):
	dp.append([INF] * (N + 1))
dp[0][0] = 0

def hitman_available(hitman, mask):
	return not 2 << hitman & mask

def use_hitman(hitman, mask):
	return mask | 2 << hitman
for already_killed in range(N):
	for mask in range(MASK):
		for hitman in range(K):
			if hitman_available(hitman, mask):
				mask_after = use_hitman(hitman, mask)
				for num_to_kill in range(1, N - already_killed + 1):
					dp[mask_after][num_to_kill + already_killed] = min(dp[mask_after][num_to_kill + already_killed], dp[mask][already_killed] + sum(cost[hitman][already_killed:already_killed + num_to_kill]))
print(min((dp[i][N] for i in range(MASK))))


import os
import sys
(N, K) = map(int, input().split())
cost = []
MASK = 2 << K
INF = 10 ** 8 - 1
for i in range(K):
	prices = list(map(int, input().split()))
	prices.reverse()
	cost.append(prices)
dp = []
for i in range(MASK):
	dp.append([INF] * (N + 1))
dp[0][0] = 0

def hitman_available(hitman, mask):
	return not 2 << hitman & mask

def use_hitman(hitman, mask):
	return mask | 2 << hitman
for already_killed in range(N):
	for mask in range(MASK):
		for hitman in range(K):
			if hitman_available(hitman, mask):
				mask_after = use_hitman(hitman, mask)
				for num_to_kill in range(1, N - already_killed + 1):
					dp[mask_after][num_to_kill + already_killed] = min(dp[mask_after][num_to_kill + already_killed], dp[mask][already_killed] + sum(cost[hitman][already_killed:already_killed + num_to_kill]))
print(min((dp[i][N] for i in range(MASK))))


import os
import sys
(N, K) = map(int, input().split())
cost = []
MASK = 2 << K
INF = 10 ** 8 - 1
for i in range(K):
	prices = list(map(int, input().split()))
	prices.reverse()
	cost.append(prices)
dp = []
for i in range(MASK):
	dp.append([INF] * (N + 1))
dp[0][0] = 0

def hitman_available(hitman, mask):
	return not 2 << hitman & mask

def use_hitman(hitman, mask):
	return mask | 2 << hitman
for already_killed in range(N):
	for mask in range(MASK):
		for hitman in range(K):
			if hitman_available(hitman, mask):
				mask_after = use_hitman(hitman, mask)
				for num_to_kill in range(1, N - already_killed + 1):
					dp[mask_after][num_to_kill + already_killed] = min(dp[mask_after][num_to_kill + already_killed], dp[mask][already_killed] + sum(cost[hitman][already_killed:already_killed + num_to_kill]))
print(min((dp[i][N] for i in range(MASK))))


import os
import sys
(N, K) = map(int, input().split())
cost = []
MASK = 2 << K
INF = 10 ** 8 - 1
for i in range(K):
	prices = list(map(int, input().split()))
	prices.reverse()
	cost.append(prices)
dp = []
for i in range(MASK):
	dp.append([INF] * (N + 1))
dp[0][0] = 0

def hitman_available(hitman, mask):
	return not 2 << hitman & mask

def use_hitman(hitman, mask):
	return mask | 2 << hitman
for already_killed in range(N):
	for mask in range(MASK):
		for hitman in range(K):
			if hitman_available(hitman, mask):
				mask_after = use_hitman(hitman, mask)
				for num_to_kill in range(1, N - already_killed + 1):
					dp[mask_after][num_to_kill + already_killed] = min(dp[mask_after][num_to_kill + already_killed], dp[mask][already_killed] + sum(cost[hitman][already_killed:already_killed + num_to_kill]))
print(min((dp[i][N] for i in range(MASK))))


(G, M) = [int(s) for s in input().split()]
costs = list()
cache = dict()
for i in range(M):
	costs.append([int(s) for s in input().split()])

def kill(gn, imercs):
	key = str(gn) + str(imercs)
	if key in cache:
		return cache[key]
	mercs = imercs[:]
	if gn == 0:
		return 0
	temp = list()
	for m in mercs:
		tempm = mercs[:]
		tempm.remove(m)
		if len(tempm) == 0:
			temp.append(sum(costs[m][:gn]))
		else:
			for c in range(gn - 1, -1, -1):
				temp.append(sum(costs[m][c:gn]) + kill(c, tempm))
	cache[key] = min(temp)
	return min(temp)
print(str(kill(G, [i for i in range(M)])))


import os
import sys
(N, K) = map(int, input().split())
cost = []
MASK = 2 << K
INF = 10 ** 8 - 1
for i in range(K):
	prices = list(map(int, input().split()))
	prices.reverse()
	cost.append(prices)
dp = []
for i in range(MASK):
	dp.append([INF] * (N + 1))
dp[0][0] = 0

def hitman_available(hitman, mask):
	return not 2 << hitman & mask

def use_hitman(hitman, mask):
	return mask | 2 << hitman
for already_killed in range(N):
	for mask in range(MASK):
		for hitman in range(K):
			if hitman_available(hitman, mask):
				mask_after = use_hitman(hitman, mask)
				for num_to_kill in range(1, N - already_killed + 1):
					dp[mask_after][num_to_kill + already_killed] = min(dp[mask_after][num_to_kill + already_killed], dp[mask][already_killed] + sum(cost[hitman][already_killed:already_killed + num_to_kill]))
print(min((dp[i][N] for i in range(MASK))))


import os
import sys
(N, K) = map(int, input().split())
cost = []
MASK = 2 << K
INF = 10 ** 8 - 1
for i in range(K):
	prices = list(map(int, input().split()))
	prices.reverse()
	cost.append(prices)
dp = []
for i in range(MASK):
	dp.append([INF] * (N + 1))
dp[0][0] = 0

def hitman_available(hitman, mask):
	return not 2 << hitman & mask

def use_hitman(hitman, mask):
	return mask | 2 << hitman
for already_killed in range(N):
	for mask in range(MASK):
		for hitman in range(K):
			if hitman_available(hitman, mask):
				mask_after = use_hitman(hitman, mask)
				for num_to_kill in range(1, N - already_killed + 1):
					dp[mask_after][num_to_kill + already_killed] = min(dp[mask_after][num_to_kill + already_killed], dp[mask][already_killed] + sum(cost[hitman][already_killed:already_killed + num_to_kill]))
print(min((dp[i][N] for i in range(MASK))))


import os
import sys
(N, K) = map(int, input().split())
cost = []
MASK = 2 << K
INF = 10 ** 8 - 1
for i in range(K):
	prices = list(map(int, input().split()))
	prices.reverse()
	cost.append(prices)
dp = []
for i in range(MASK):
	dp.append([INF] * (N + 1))
dp[0][0] = 0

def hitman_available(hitman, mask):
	return not 2 << hitman & mask

def use_hitman(hitman, mask):
	return mask | 2 << hitman
for already_killed in range(N):
	for mask in range(MASK):
		for hitman in range(K):
			if hitman_available(hitman, mask):
				mask_after = use_hitman(hitman, mask)
				for num_to_kill in range(1, N - already_killed + 1):
					dp[mask_after][num_to_kill + already_killed] = min(dp[mask_after][num_to_kill + already_killed], dp[mask][already_killed] + sum(cost[hitman][already_killed:already_killed + num_to_kill]))
print(min((dp[i][N] for i in range(MASK))))


import os
import sys
(N, K) = map(int, input().split())
cost = []
MASK = 2 << K
INF = 10 ** 8 - 1
for i in range(K):
	prices = list(map(int, input().split()))
	prices.reverse()
	cost.append(prices)
dp = []
for i in range(MASK):
	dp.append([INF] * (N + 1))
dp[0][0] = 0

def hitman_available(hitman, mask):
	return not 2 << hitman & mask

def use_hitman(hitman, mask):
	return mask | 2 << hitman
for already_killed in range(N):
	for mask in range(MASK):
		for hitman in range(K):
			if hitman_available(hitman, mask):
				mask_after = use_hitman(hitman, mask)
				for num_to_kill in range(1, N - already_killed + 1):
					dp[mask_after][num_to_kill + already_killed] = min(dp[mask_after][num_to_kill + already_killed], dp[mask][already_killed] + sum(cost[hitman][already_killed:already_killed + num_to_kill]))
print(min((dp[i][N] for i in range(MASK))))


import os
import sys
(N, K) = map(int, input().split())
cost = []
MASK = 2 << K
INF = 10 ** 8 - 1
for i in range(K):
	prices = list(map(int, input().split()))
	prices.reverse()
	cost.append(prices)
dp = []
for i in range(MASK):
	dp.append([INF] * (N + 1))
dp[0][0] = 0

def hitman_available(hitman, mask):
	return not 2 << hitman & mask

def use_hitman(hitman, mask):
	return mask | 2 << hitman
for already_killed in range(N):
	for mask in range(MASK):
		for hitman in range(K):
			if hitman_available(hitman, mask):
				mask_after = use_hitman(hitman, mask)
				for num_to_kill in range(1, N - already_killed + 1):
					dp[mask_after][num_to_kill + already_killed] = min(dp[mask_after][num_to_kill + already_killed], dp[mask][already_killed] + sum(cost[hitman][already_killed:already_killed + num_to_kill]))
print(min((dp[i][N] for i in range(MASK))))


import os
import sys
(N, K) = map(int, input().split())
cost = []
MASK = 2 << K
INF = 10 ** 8 - 1
for i in range(K):
	prices = list(map(int, input().split()))
	prices.reverse()
	cost.append(prices)
dp = []
for i in range(MASK):
	dp.append([INF] * (N + 1))
dp[0][0] = 0

def hitman_available(hitman, mask):
	return not 2 << hitman & mask

def use_hitman(hitman, mask):
	return mask | 2 << hitman
for already_killed in range(N):
	for mask in range(MASK):
		for hitman in range(K):
			if hitman_available(hitman, mask):
				mask_after = use_hitman(hitman, mask)
				for num_to_kill in range(1, N - already_killed + 1):
					dp[mask_after][num_to_kill + already_killed] = min(dp[mask_after][num_to_kill + already_killed], dp[mask][already_killed] + sum(cost[hitman][already_killed:already_killed + num_to_kill]))
print(min((dp[i][N] for i in range(MASK))))


import os
import sys
(N, K) = map(int, input().split())
cost = []
MASK = 2 << K
INF = 10 ** 8 - 1
for i in range(K):
	prices = list(map(int, input().split()))
	prices.reverse()
	cost.append(prices)
dp = []
for i in range(MASK):
	dp.append([INF] * (N + 1))
dp[0][0] = 0

def hitman_available(hitman, mask):
	return not 2 << hitman & mask

def use_hitman(hitman, mask):
	return mask | 2 << hitman
for already_killed in range(N):
	for mask in range(MASK):
		for hitman in range(K):
			if hitman_available(hitman, mask):
				mask_after = use_hitman(hitman, mask)
				for num_to_kill in range(1, N - already_killed + 1):
					dp[mask_after][num_to_kill + already_killed] = min(dp[mask_after][num_to_kill + already_killed], dp[mask][already_killed] + sum(cost[hitman][already_killed:already_killed + num_to_kill]))
print(min((dp[i][N] for i in range(MASK))))


import os
import sys
(N, K) = map(int, input().split())
cost = []
MASK = 2 << K
INF = 10 ** 8 - 1
for i in range(K):
	prices = list(map(int, input().split()))
	prices.reverse()
	cost.append(prices)
dp = []
for i in range(MASK):
	dp.append([INF] * (N + 1))
dp[0][0] = 0

def hitman_available(hitman, mask):
	return not 2 << hitman & mask

def use_hitman(hitman, mask):
	return mask | 2 << hitman
for already_killed in range(N):
	for mask in range(MASK):
		for hitman in range(K):
			if hitman_available(hitman, mask):
				mask_after = use_hitman(hitman, mask)
				for num_to_kill in range(1, N - already_killed + 1):
					dp[mask_after][num_to_kill + already_killed] = min(dp[mask_after][num_to_kill + already_killed], dp[mask][already_killed] + sum(cost[hitman][already_killed:already_killed + num_to_kill]))
print(min((dp[i][N] for i in range(MASK))))


import os
import sys
(N, K) = map(int, input().split())
cost = []
MASK = 2 << K
INF = 10 ** 8 - 1
for i in range(K):
	prices = list(map(int, input().split()))
	prices.reverse()
	cost.append(prices)
dp = []
for i in range(MASK):
	dp.append([INF] * (N + 1))
dp[0][0] = 0

def hitman_available(hitman, mask):
	return not 2 << hitman & mask

def use_hitman(hitman, mask):
	return mask | 2 << hitman
for already_killed in range(N):
	for mask in range(MASK):
		for hitman in range(K):
			if hitman_available(hitman, mask):
				mask_after = use_hitman(hitman, mask)
				for num_to_kill in range(1, N - already_killed + 1):
					dp[mask_after][num_to_kill + already_killed] = min(dp[mask_after][num_to_kill + already_killed], dp[mask][already_killed] + sum(cost[hitman][already_killed:already_killed + num_to_kill]))
print(min((dp[i][N] for i in range(MASK))))


import os
import sys
(N, K) = map(int, input().split())
cost = []
MASK = 2 << K
INF = 10 ** 8 - 1
for i in range(K):
	prices = list(map(int, input().split()))
	prices.reverse()
	cost.append(prices)
dp = []
for i in range(MASK):
	dp.append([INF] * (N + 1))
dp[0][0] = 0

def hitman_available(hitman, mask):
	return not 2 << hitman & mask

def use_hitman(hitman, mask):
	return mask | 2 << hitman
for already_killed in range(N):
	for mask in range(MASK):
		for hitman in range(K):
			if hitman_available(hitman, mask):
				mask_after = use_hitman(hitman, mask)
				for num_to_kill in range(1, N - already_killed + 1):
					dp[mask_after][num_to_kill + already_killed] = min(dp[mask_after][num_to_kill + already_killed], dp[mask][already_killed] + sum(cost[hitman][already_killed:already_killed + num_to_kill]))
print(min((dp[i][N] for i in range(MASK))))


import os
import sys
(N, K) = map(int, input().split())
cost = []
MASK = 2 << K
INF = 10 ** 8 - 1
for i in range(K):
	prices = list(map(int, input().split()))
	prices.reverse()
	cost.append(prices)
dp = []
for i in range(MASK):
	dp.append([INF] * (N + 1))
dp[0][0] = 0

def hitman_available(hitman, mask):
	return not 2 << hitman & mask

def use_hitman(hitman, mask):
	return mask | 2 << hitman
for already_killed in range(N):
	for mask in range(MASK):
		for hitman in range(K):
			if hitman_available(hitman, mask):
				mask_after = use_hitman(hitman, mask)
				for num_to_kill in range(1, N - already_killed + 1):
					dp[mask_after][num_to_kill + already_killed] = min(dp[mask_after][num_to_kill + already_killed], dp[mask][already_killed] + sum(cost[hitman][already_killed:already_killed + num_to_kill]))
print(min((dp[i][N] for i in range(MASK))))


import os
import sys
(N, K) = map(int, input().split())
cost = []
MASK = 2 << K
INF = 10 ** 8 - 1
for i in range(K):
	prices = list(map(int, input().split()))
	prices.reverse()
	cost.append(prices)
dp = []
for i in range(MASK):
	dp.append([INF] * (N + 1))
dp[0][0] = 0

def hitman_available(hitman, mask):
	return not 2 << hitman & mask

def use_hitman(hitman, mask):
	return mask | 2 << hitman
for already_killed in range(N):
	for mask in range(MASK):
		for hitman in range(K):
			if hitman_available(hitman, mask):
				mask_after = use_hitman(hitman, mask)
				for num_to_kill in range(1, N - already_killed + 1):
					dp[mask_after][num_to_kill + already_killed] = min(dp[mask_after][num_to_kill + already_killed], dp[mask][already_killed] + sum(cost[hitman][already_killed:already_killed + num_to_kill]))
print(min((dp[i][N] for i in range(MASK))))


import os
import sys
(N, K) = map(int, input().split())
cost = []
MASK = 2 << K
INF = 10 ** 8 - 1
for i in range(K):
	prices = list(map(int, input().split()))
	prices.reverse()
	cost.append(prices)
dp = []
for i in range(MASK):
	dp.append([INF] * (N + 1))
dp[0][0] = 0

def hitman_available(hitman, mask):
	return not 2 << hitman & mask

def use_hitman(hitman, mask):
	return mask | 2 << hitman
for already_killed in range(N):
	for mask in range(MASK):
		for hitman in range(K):
			if hitman_available(hitman, mask):
				mask_after = use_hitman(hitman, mask)
				for num_to_kill in range(1, N - already_killed + 1):
					dp[mask_after][num_to_kill + already_killed] = min(dp[mask_after][num_to_kill + already_killed], dp[mask][already_killed] + sum(cost[hitman][already_killed:already_killed + num_to_kill]))
print(min((dp[i][N] for i in range(MASK))))


import os
import sys
(N, K) = map(int, input().split())
cost = []
MASK = 2 << K
INF = 10 ** 8 - 1
for i in range(K):
	prices = list(map(int, input().split()))
	prices.reverse()
	cost.append(prices)
dp = []
for i in range(MASK):
	dp.append([INF] * (N + 1))
dp[0][0] = 0

def hitman_available(hitman, mask):
	return not 2 << hitman & mask

def use_hitman(hitman, mask):
	return mask | 2 << hitman
for already_killed in range(N):
	for mask in range(MASK):
		for hitman in range(K):
			if hitman_available(hitman, mask):
				mask_after = use_hitman(hitman, mask)
				for num_to_kill in range(1, N - already_killed + 1):
					dp[mask_after][num_to_kill + already_killed] = min(dp[mask_after][num_to_kill + already_killed], dp[mask][already_killed] + sum(cost[hitman][already_killed:already_killed + num_to_kill]))
print(min((dp[i][N] for i in range(MASK))))


import os
import sys
(N, K) = map(int, input().split())
cost = []
MASK = 2 << K
INF = 10 ** 8 - 1
for i in range(K):
	prices = list(map(int, input().split()))
	prices.reverse()
	cost.append(prices)
dp = []
for i in range(MASK):
	dp.append([INF] * (N + 1))
dp[0][0] = 0

def hitman_available(hitman, mask):
	return not 2 << hitman & mask

def use_hitman(hitman, mask):
	return mask | 2 << hitman
for already_killed in range(N):
	for mask in range(MASK):
		for hitman in range(K):
			if hitman_available(hitman, mask):
				mask_after = use_hitman(hitman, mask)
				for num_to_kill in range(1, N - already_killed + 1):
					dp[mask_after][num_to_kill + already_killed] = min(dp[mask_after][num_to_kill + already_killed], dp[mask][already_killed] + sum(cost[hitman][already_killed:already_killed + num_to_kill]))
print(min((dp[i][N] for i in range(MASK))))


import os
import sys
(N, K) = map(int, input().split())
cost = []
MASK = 2 << K
INF = 10 ** 8 - 1
for i in range(K):
	prices = list(map(int, input().split()))
	prices.reverse()
	cost.append(prices)
dp = []
for i in range(MASK):
	dp.append([INF] * (N + 1))
dp[0][0] = 0

def hitman_available(hitman, mask):
	return not 2 << hitman & mask

def use_hitman(hitman, mask):
	return mask | 2 << hitman
for already_killed in range(N):
	for mask in range(MASK):
		for hitman in range(K):
			if hitman_available(hitman, mask):
				mask_after = use_hitman(hitman, mask)
				for num_to_kill in range(1, N - already_killed + 1):
					dp[mask_after][num_to_kill + already_killed] = min(dp[mask_after][num_to_kill + already_killed], dp[mask][already_killed] + sum(cost[hitman][already_killed:already_killed + num_to_kill]))
print(min((dp[i][N] for i in range(MASK))))


import os
import sys
(N, K) = map(int, input().split())
cost = []
MASK = 2 << K
INF = 10 ** 8 - 1
for i in range(K):
	prices = list(map(int, input().split()))
	prices.reverse()
	cost.append(prices)
dp = []
for i in range(MASK):
	dp.append([INF] * (N + 1))
dp[0][0] = 0

def hitman_available(hitman, mask):
	return not 2 << hitman & mask

def use_hitman(hitman, mask):
	return mask | 2 << hitman
for already_killed in range(N):
	for mask in range(MASK):
		for hitman in range(K):
			if hitman_available(hitman, mask):
				mask_after = use_hitman(hitman, mask)
				for num_to_kill in range(1, N - already_killed + 1):
					dp[mask_after][num_to_kill + already_killed] = min(dp[mask_after][num_to_kill + already_killed], dp[mask][already_killed] + sum(cost[hitman][already_killed:already_killed + num_to_kill]))
print(min((dp[i][N] for i in range(MASK))))


import os
import sys
(N, K) = map(int, input().split())
cost = []
MASK = 2 << K
INF = 10 ** 8 - 1
for i in range(K):
	prices = list(map(int, input().split()))
	prices.reverse()
	cost.append(prices)
dp = []
for i in range(MASK):
	dp.append([INF] * (N + 1))
dp[0][0] = 0

def hitman_available(hitman, mask):
	return not 2 << hitman & mask

def use_hitman(hitman, mask):
	return mask | 2 << hitman
for already_killed in range(N):
	for mask in range(MASK):
		for hitman in range(K):
			if hitman_available(hitman, mask):
				mask_after = use_hitman(hitman, mask)
				for num_to_kill in range(1, N - already_killed + 1):
					dp[mask_after][num_to_kill + already_killed] = min(dp[mask_after][num_to_kill + already_killed], dp[mask][already_killed] + sum(cost[hitman][already_killed:already_killed + num_to_kill]))
print(min((dp[i][N] for i in range(MASK))))


import os
import sys
(N, K) = map(int, input().split())
cost = []
MASK = 2 << K
INF = 10 ** 8 - 1
for i in range(K):
	prices = list(map(int, input().split()))
	prices.reverse()
	cost.append(prices)
dp = []
for i in range(MASK):
	dp.append([INF] * (N + 1))
dp[0][0] = 0

def hitman_available(hitman, mask):
	return not 2 << hitman & mask

def use_hitman(hitman, mask):
	return mask | 2 << hitman
for already_killed in range(N):
	for mask in range(MASK):
		for hitman in range(K):
			if hitman_available(hitman, mask):
				mask_after = use_hitman(hitman, mask)
				for num_to_kill in range(1, N - already_killed + 1):
					dp[mask_after][num_to_kill + already_killed] = min(dp[mask_after][num_to_kill + already_killed], dp[mask][already_killed] + sum(cost[hitman][already_killed:already_killed + num_to_kill]))
print(min((dp[i][N] for i in range(MASK))))


import os
import sys
(N, K) = map(int, input().split())
cost = []
MASK = 2 << K
INF = 10 ** 8 - 1
for i in range(K):
	prices = list(map(int, input().split()))
	prices.reverse()
	cost.append(prices)
dp = []
for i in range(MASK):
	dp.append([INF] * (N + 1))
dp[0][0] = 0

def hitman_available(hitman, mask):
	return not 2 << hitman & mask

def use_hitman(hitman, mask):
	return mask | 2 << hitman
for already_killed in range(N):
	for mask in range(MASK):
		for hitman in range(K):
			if hitman_available(hitman, mask):
				mask_after = use_hitman(hitman, mask)
				for num_to_kill in range(1, N - already_killed + 1):
					dp[mask_after][num_to_kill + already_killed] = min(dp[mask_after][num_to_kill + already_killed], dp[mask][already_killed] + sum(cost[hitman][already_killed:already_killed + num_to_kill]))
print(min((dp[i][N] for i in range(MASK))))