There is a row of N walls in Geeksland. The king of Geeksland ordered Alexa to color all the walls on the occasion of New Year. Alexa can color each wall with one of the K colors. The cost associated with coloring each wall with a particular color is represented by a 2D costs array of size N * K. For example, costs[0][0] is the cost of coloring wall 0 with color 0; costs[1][2] is the cost of coloring wall 1 with color 2, and so on... Find the minimum cost to color all the walls such that no two adjacent walls have the same color.
Note: If you are not able to paint all the walls, then you should return -1.
Example 1:
Input:
N = 4, K = 3
costs[][] = {{1, 5, 7},
             {5, 8, 4},
             {3, 2, 9},
             {1, 2, 4}}
Output:
8
Explanation:
Paint wall 0 with color 0. Cost = 1
Paint wall 1 with color 2. Cost = 4
Paint wall 2 with color 1. Cost = 2
Paint wall 3 with color 0. Cost = 1
Total Cost = 1 + 4 + 2 + 1 = 8
Example 2:
Input:
N = 5, K = 1
costs[][] = {{5},
             {4},
             {9},
             {2},
             {1}}
Output:
-1
Explanation:
It is not possible to color all the walls under the given conditions.
Your Task:
Your task is to complete the function minCost() which takes a 2D integer matrix costs as the only argument and returns an integer, representing the minimum cost to paint all the walls. If you are not able to paint all the walls, then you should return -1
Expected Time Complexity: O(N*K)
Expected Space Complexity: O(N*K)
Constraints:
	0 <= N <= 10^{3}
	0 <= K <= 10^{3}
	1 <= costs[i][j] <= 10^{5}

Source: geeksforgeeks | Difficulty: MEDIUM_HARD
Tags: Dynamic programming

Starter code: #User function Template for python3



class Solution:

    def minCost(self, costs : List[List[int]]) -> int:

        #your code goes here

Solutions:
from typing import List
inf = 10 ** 18

class Solution:

	def minCost(self, costs: List[List[int]]) -> int:
		(n, k) = (len(costs), len(costs[0]))
		if k == 1 and n > 1:
			return -1
		nmin = [[0, -1], [0, -1]]
		for i in range(1, n + 1):
			min1 = nmin[:]
			nmin = []
			for j in range(1, k + 1):
				mini = min1[0]
				if mini[1] == j - 1:
					mini = min1[1]
				cost = [costs[i - 1][j - 1] + mini[0], j - 1]
				nmin.append(cost)
				nmin.sort()
				nmin = nmin[:2]
		return nmin[0][0]


class Solution:

	def minCost(self, costs) -> int:
		if len(costs) > 1 and len(costs[0]) == 1:
			return -1
		lowPrev = [-1, 10000001, 10000001]
		lowhere = []
		for i in range(len(costs)):
			lowHere = [-1, 10000001, 10000001]
			for j in range(len(costs[i])):
				if i == 0:
					if costs[i][j] < lowHere[1]:
						(lowHere[0], lowHere[1], lowHere[2]) = (j, costs[i][j], lowHere[1])
					elif costs[i][j] < lowHere[2]:
						lowHere[2] = costs[i][j]
					lowPrev = lowHere
				else:
					local = costs[i][j] + (lowPrev[2] if j == lowPrev[0] else lowPrev[1])
					if local < lowHere[1]:
						(lowHere[0], lowHere[1], lowHere[2]) = (j, local, lowHere[1])
					elif local < lowHere[2]:
						lowHere[2] = local
			lowPrev = lowHere
		return lowHere[1]


class Solution:

	def minCost(self, costs) -> int:
		N = len(costs)
		K = len(costs[0])
		if K == 1 and N > 1:
			return -1
		if K == 1 and N == 1:
			return costs[0][0]
		rem = [0 for i in range(K)]
		min1 = [10 ** 7, 0]
		for j in range(K):
			rem[j] = costs[0][j]
			if min1[0] > rem[j]:
				min1[0] = rem[j]
				min1[1] = j
		min2 = 10 ** 7
		for j in range(K):
			if j == min1[1]:
				continue
			elif min2 > rem[j]:
				min2 = rem[j]
		for i in range(1, N):
			for j in range(K):
				if j == min1[1]:
					rem[j] = costs[i][j] + min2
				else:
					rem[j] = costs[i][j] + min1[0]
			min1 = [10 ** 7, 0]
			min2 = 10 ** 7
			for j in range(K):
				if min1[0] > rem[j]:
					min1[0] = rem[j]
					min1[1] = j
			for j in range(K):
				if j == min1[1]:
					continue
				elif min2 > rem[j]:
					min2 = rem[j]
		return min1[0]


from typing import List

class Solution:

	def minCost(self, costs: List[List[int]]) -> int:
		N = len(costs)
		K = len(costs[0])
		if K == 1 and N > 1:
			return -1
		dp = [[0 for _ in range(K)] for _ in range(N)]
		(min1, min2) = (0, 0)
		argmin = None
		for i in range(N):
			(new_min1, new_min2) = (10000000, 10000000)
			new_argmin = None
			for j in range(K):
				if i == 0:
					dp[i][j] = costs[i][j]
				elif j == argmin:
					dp[i][j] = min2 + costs[i][j]
				else:
					dp[i][j] = min1 + costs[i][j]
				if dp[i][j] < new_min1:
					new_argmin = j
					new_min2 = new_min1
					new_min1 = dp[i][j]
				else:
					new_min2 = min(dp[i][j], new_min2)
			min1 = new_min1
			min2 = new_min2
			argmin = new_argmin
		return min1


class Solution:

	def minCost(self, costs) -> int:
		if len(costs[0]) == 1 and len(costs) > 1:
			return -1
		elif len(costs) == 1:
			return min(costs[0])
		else:
			N = len(costs)
			k = len(costs[0])
			dp = [[0] * k for i in range(N)]
			dp[0] = costs[0]
			min1 = 10000000000
			min2 = 10000000001
			for i in costs[0]:
				if i < min1:
					min2 = min1
					min1 = i
				elif i < min2:
					min2 = i
			for i in range(1, N):
				temp1 = 1000000000
				temp2 = 1000000001
				for j in range(k):
					if min1 == dp[i - 1][j]:
						dp[i][j] = min2 + costs[i][j]
					else:
						dp[i][j] = min1 + costs[i][j]
					if dp[i][j] <= temp1:
						temp2 = temp1
						temp1 = dp[i][j]
					elif dp[i][j] < temp2:
						temp2 = dp[i][j]
				min1 = temp1
				min2 = temp2
			return min1


from heapq import heappushpop
from math import inf
from typing import List

class Solution:

	def minCost(self, costs: List[List[int]]) -> int:
		(n, k) = (len(costs), len(costs[0]))
		heap = [(0, 1), (0, 0)]
		dp = [0] * k
		for i in range(n):
			new_heap = [(-inf, 1), (-inf, 0)]
			for j in range(k):
				dp[j] = costs[i][j] - (heap[1][0] if heap[1][1] != j else heap[0][0])
				heappushpop(new_heap, (-dp[j], j))
			heap = new_heap
		res = min(dp)
		return res if res != inf else -1


from typing import List
import copy
import numpy as np
import math

class Solution:

	def minCost1(self, costs: List[List[int]]) -> int:
		result = copy.copy(costs[0])
		calc1 = [0] * len(result)
		calc2 = [0] * len(result)
		for nj in range(1, len(costs)):
			for ni in range(0, len(costs[nj])):
				for nk in range(0, len(result)):
					if ni != nk:
						calc1[nk] = result[nk] + costs[nj][ni]
					else:
						calc1[nk] = 9999999999999
				calc2[ni] = min(calc1)
			result = copy.copy(calc2)
		if min(result) == 9999999999999:
			return -1
		else:
			return min(result)

	def minCost2(self, costs: List[List[int]]) -> int:
		njj = len(costs)
		nii = len(costs[0])
		result = np.array(costs[0])
		calc1 = np.array([0] * nii)
		calc2 = np.array([0] * nii)
		for nj in range(1, njj):
			for ni in range(nii):
				calc1 = result + costs[nj][ni]
				calc1[ni] = 9999999999999
				calc2[ni] = min(calc1)
			result = np.array(calc2)
		if min(result) == 9999999999999:
			return -1
		else:
			return min(result)

	def minCost_good(self, costs: List[List[int]]) -> int:
		njj = len(costs)
		nii = len(costs[0])
		verylargeno = 9999999999999
		result = np.array(costs[0])
		for nj in range(1, njj):
			calc1 = np.transpose(np.zeros((nii, 1)) + result) + np.array(costs[nj])
			np.fill_diagonal(calc1, verylargeno)
			result = np.amin(calc1, axis=0)
		if min(result) == verylargeno:
			return -1
		else:
			return int(min(result))

	def second_smallest(self, numbers):
		m1 = m2 = float('inf')
		for x in numbers:
			if x <= m1:
				(m1, m2) = (x, m1)
			elif x < m2:
				m2 = x
		return m2

	def second_smallest_position(self, numbers):
		m1 = m2 = float('inf')
		ni = 0
		result = 0
		for x in numbers:
			if x <= m1:
				(m1, m2) = (x, m1)
			elif x < m2:
				m2 = x
				result = ni
			ni = ni + 1
		return result

	def the_smallest(self, numbers):
		return min(numbers)

	def the_smallest_position(self, numbers):
		m1 = float('inf')
		ni = 0
		result = 0
		for x in numbers:
			if x <= m1:
				m1 = x
				result = ni
			ni = ni + 1
		return result

	def minCost(self, costs: List[List[int]]) -> int:
		njj = len(costs)
		nii = len(costs[0])
		s1 = self.the_smallest(costs[0])
		s1p = self.the_smallest_position(costs[0])
		s2 = self.second_smallest(costs[0])
		s2p = self.second_smallest_position(costs[0])
		for nj in range(1, njj):
			calc1 = [99999999] * len(costs[0])
			for ni in range(nii):
				if ni != s1p:
					calc1[ni] = min(calc1[ni], s1 + costs[nj][ni])
				if ni != s2p:
					calc1[ni] = min(calc1[ni], s2 + costs[nj][ni])
			s1 = self.the_smallest(calc1)
			s1p = self.the_smallest_position(calc1)
			s2 = self.second_smallest(calc1)
			s2p = self.second_smallest_position(calc1)
		if s1 == 99999999:
			return -1
		else:
			return s1


class Solution:

	def minCost(self, costs):
		N = len(costs)
		K = len(costs[0])
		firstS = float('inf')
		secondS = float('inf')
		if K == 1 and N == 1:
			return costs[0][0]
		if K == 1:
			return -1
		for i in range(0, K):
			if costs[0][i] < firstS:
				secondS = firstS
				firstS = costs[0][i]
			elif costs[0][i] < secondS:
				secondS = costs[0][i]
		for i in range(1, N):
			for j in range(0, K):
				if firstS != costs[i - 1][j]:
					costs[i][j] += firstS
				else:
					costs[i][j] += secondS
			firstS = float('inf')
			secondS = float('inf')
			for j in range(0, K):
				if costs[i][j] < firstS:
					secondS = firstS
					firstS = costs[i][j]
				elif costs[i][j] < secondS:
					secondS = costs[i][j]
		return sorted(costs[N - 1])[0]


class Solution:

	def minCost(self, costs):
		n = len(costs)
		k = len(costs[0])
		dp = [[float('inf') for _ in range(n)] for _ in range(k)]
		first_min = float('inf')
		second_min = float('inf')
		for j in range(k):
			dp[j][0] = costs[0][j]
			if costs[0][j] < first_min:
				second_min = first_min
				first_min = costs[0][j]
			elif costs[0][j] < second_min:
				second_min = costs[0][j]
		for i in range(1, n):
			c_min = float('inf')
			s_min = float('inf')
			for j in range(k):
				if dp[j][i - 1] == first_min:
					dp[j][i] = costs[i][j] + second_min
				else:
					dp[j][i] = costs[i][j] + first_min
				if dp[j][i] < c_min:
					s_min = c_min
					c_min = dp[j][i]
				elif dp[j][i] < s_min:
					s_min = dp[j][i]
			first_min = c_min
			second_min = s_min
		if first_min == float('inf'):
			return -1
		return first_min


class Solution:

	def minCost(self, c):
		n = len(c)
		m = len(c[0])
		if m == 1:
			if n == 1:
				return c[0][0]
			else:
				return -1
		prev1 = [100000000000, -1]
		prev2 = [100000000000, -1]
		for i in range(0, m):
			if c[0][i] < prev1[0]:
				prev2 = prev1
				prev1 = [c[0][i], i]
			elif c[0][i] < prev2[0]:
				prev2 = [c[0][i], i]
		for i in range(1, n):
			curr1 = [100000000000, -1]
			curr2 = [100000000000, -1]
			for j in range(0, m):
				x = c[i][j]
				if j != prev1[1]:
					x += prev1[0]
				else:
					x += prev2[0]
				if x < curr1[0]:
					curr2 = curr1
					curr1 = [x, j]
				elif x < curr2[0]:
					curr2 = [x, j]
			prev1 = curr1
			prev2 = curr2
		return prev1[0]


from typing import List

class Solution:

	def minCost(self, costs: List[List[int]]) -> int:
		(n, k) = (len(costs), len(costs[0]))
		if n == 1:
			return min(costs[0])
		if k == 1:
			return -1
		for i in range(1, n):
			a = b = -1
			for j in range(k):
				if a == -1 or costs[i - 1][j] < costs[i - 1][a]:
					b = a
					a = j
				elif b == -1 or costs[i - 1][j] < costs[i - 1][b]:
					b = j
			for j in range(k):
				if j != a:
					costs[i][j] += costs[i - 1][a]
				else:
					costs[i][j] += costs[i - 1][b]
		return min(costs[n - 1])


class Solution:

	def minCost(self, dp):
		(n, m) = (len(dp), len(dp[0]))
		if m == 1 and n > 1:
			return -1
		for idx in range(n - 2, -1, -1):
			suff = [float('inf')] * (m + 1)
			for i in reversed(range(m)):
				suff[i] = min(suff[i + 1], dp[idx + 1][i])
			pref = float('inf')
			for i in range(m):
				dp[idx][i] = dp[idx][i] + min(pref, suff[i + 1])
				pref = min(pref, dp[idx + 1][i])
		return min(dp[0])


from typing import List
import sys

class Solution:

	def minCost(self, costs: List[List[int]]) -> int:
		i = 0
		for i in range(1, len(costs)):
			c = -1
			m = sys.maxsize
			n = sys.maxsize
			for k in range(0, len(costs[i])):
				if m > costs[i - 1][k]:
					c = k
					m = costs[i - 1][k]
			for k in range(0, len(costs[i])):
				if n > costs[i - 1][k] and k != c:
					n = costs[i - 1][k]
			if m == sys.maxsize:
				return -1
			for j in range(0, len(costs[i])):
				if j != c:
					costs[i][j] += m
				else:
					costs[i][j] += n
		if min(costs[i]) >= sys.maxsize:
			return -1
		return min(costs[i])


class Solution:

	def minCost(self, costs):
		N = len(costs)
		K = len(costs[0])
		if K == 1:
			if N == 1:
				return costs[0][0]
			else:
				return -1
		(m1, m2) = sorted(costs[0])[0:2]
		for i in range(1, N):
			for j in range(K):
				if m1 == costs[i - 1][j]:
					costs[i][j] += m2
				else:
					costs[i][j] += m1
			(m1, m2) = sorted(costs[i])[0:2]
		return min(costs[-1])


from typing import List

def min2(a):
	i1 = 0
	for i in range(0, len(a)):
		if a[i] < a[i1]:
			i1 = i
	i2 = 0 if i1 != 0 else 1
	for i in range(0, len(a)):
		if i != i1 and a[i] < a[i2]:
			i2 = i
	return (i1, i2)

class Solution:

	def minCost(self, costs: List[List[int]]) -> int:
		n = len(costs)
		k = len(costs[0])
		if k == 1:
			if n == 1:
				return costs[0][0]
			else:
				return -1
		dp = [[0] * k for _ in range(n)]
		for i in range(1, n):
			(i1, i2) = min2(costs[i - 1])
			c1 = costs[i - 1][i1]
			c2 = costs[i - 1][i2]
			for j in range(k):
				if j != i1:
					costs[i][j] += c1
				else:
					costs[i][j] += c2
		return min(costs[-1])


from typing import List
from heapq import heappush, heappop
from collections import namedtuple
MinWallCol = namedtuple('MinWallCol', 'cost color')
MAX_COST = int(100000000.0)

class Solution:

	def minCost(self, costs: List[List[int]]) -> int:
		N = len(costs)
		K = len(costs[0])
		if N == 0:
			return 0
		if N == 1:
			return min(costs[0])
		if K < 2:
			return -1
		prev_min = MinWallCol(0, -1)
		prev_snd_min = MinWallCol(0, -1)
		for i in range(N):
			curr_min = MinWallCol(MAX_COST, -1)
			curr_snd_min = MinWallCol(MAX_COST, -1)
			for (j, cost) in enumerate(costs[i]):
				if j != prev_min.color:
					new_cost = prev_min.cost + cost
				else:
					new_cost = prev_snd_min.cost + cost
				if new_cost < curr_min.cost:
					curr_snd_min = curr_min
					curr_min = MinWallCol(new_cost, j)
				elif new_cost < curr_snd_min.cost:
					curr_snd_min = MinWallCol(new_cost, j)
			prev_min = curr_min
			prev_snd_min = curr_snd_min
		return prev_min.cost


class Solution:

	def minCost(self, costs):
		N = len(costs)
		K = len(costs[0])
		if K == 1 and N > 1:
			return -1
		if K == 1 and N == 1:
			return costs[0][0]
		rem = [0 for i in range(K)]
		min1 = [10 ** 7, 0]
		for j in range(K):
			rem[j] = costs[0][j]
			if min1[0] > rem[j]:
				min1[0] = rem[j]
				min1[1] = j
		min2 = 10 ** 7
		for j in range(K):
			if j == min1[1]:
				continue
			elif min2 > rem[j]:
				min2 = rem[j]
		for i in range(1, N):
			for j in range(K):
				if j == min1[1]:
					rem[j] = costs[i][j] + min2
				else:
					rem[j] = costs[i][j] + min1[0]
			min1 = [10 ** 7, 0]
			min2 = 10 ** 7
			for j in range(K):
				if min1[0] > rem[j]:
					min1[0] = rem[j]
					min1[1] = j
			for j in range(K):
				if j == min1[1]:
					continue
				elif min2 > rem[j]:
					min2 = rem[j]
		return min1[0]
		N = len(costs)
		K = len(costs[0])
		if K == 1:
			if N == 1:
				return costs[0][0]
			else:
				return -1
		(m1, m2) = sorted(costs[0])[0:2]
		for i in range(1, N):
			for j in range(K):
				if m1 == costs[i - 1][j]:
					costs[i][j] += m2
				else:
					costs[i][j] += m1
			(m1, m2) = sorted(costs[i])[0:2]
		return min(costs[-1])


import typing

class Solution:

	def minCost(self, costs):
		dp = [[costs[j][i] for i in range(len(costs[0]))] for j in range(len(costs))]
		x = dp[0][0]
		mn = [float('inf') for i in range(len(costs[0]))]
		for i in range(1, len(costs[0])):
			mn[i] = min(mn[i], x)
			x = min(x, dp[0][i])
		x = dp[0][-1]
		for i in range(len(costs[0]) - 2, -1, -1):
			mn[i] = min(mn[i], x)
			x = min(x, dp[0][i])
		for i in range(1, len(costs)):
			for j in range(len(costs[i])):
				dp[i][j] = dp[i][j] + mn[j]
			mn[0] = float('inf')
			x = dp[i][0]
			for p in range(1, len(costs[0])):
				mn[p] = x
				x = min(x, dp[i][p])
			x = dp[i][-1]
			for p in range(len(costs[0]) - 2, -1, -1):
				mn[p] = min(mn[p], x)
				x = min(x, dp[i][p])
		ans = min(dp[-1])
		return ans if ans != float('inf') else -1


from typing import List

class Solution:

	def minCost(self, costs: List[List[int]]) -> int:
		N = len(costs)
		if N == 0:
			return 0
		K = len(costs[0])
		if K == 0 or (N > 1 and K == 1):
			return -1
		best = secondbest = float('inf')
		bestindex = 0
		for j in range(K):
			if costs[0][j] <= best:
				secondbest = best
				best = costs[0][j]
				bestindex = j
			elif costs[0][j] < secondbest:
				secondbest = costs[0][j]
		for i in range(1, N):
			nextbest = nextsecondbest = float('inf')
			nextbestindex = 0
			for j in range(K):
				mincost = best if bestindex != j else secondbest
				cost = mincost + costs[i][j]
				if cost <= nextbest:
					nextsecondbest = nextbest
					nextbest = cost
					nextbestindex = j
				elif cost < nextsecondbest:
					nextsecondbest = cost
			best = nextbest
			secondbest = nextsecondbest
			bestindex = nextbestindex
		return best


class Solution:

	def minCost(self, costs) -> int:
		from heapq import heappushpop, heappush, heappop
		if len(costs) == 1:
			return min(costs[0])
		if len(costs[0]) == 1:
			return -1
		(n, k) = (len(costs), len(costs[0]))
		dp = [[0] * k for _ in range(n + 1)]
		(min1, min2) = ((0, None), (0, None))
		h = []
		for wall in range(n):
			for color in range(k):
				dp[wall + 1][color] = (min1[0] if min1[1] != color else min2[0]) + costs[wall][color]
				if len(h) < 2:
					heappush(h, (-dp[wall + 1][color], color))
				else:
					heappushpop(h, (-dp[wall + 1][color], color))
			min2 = heappop(h)
			min2 = (min2[0] * -1, min2[1])
			min1 = heappop(h)
			min1 = (min1[0] * -1, min1[1])
		return min1[0]


import sys

class Solution:

	def minCost(self, costs) -> int:
		n = len(costs)
		if n == 0:
			return -1
		k = len(costs[0])
		if n == 1:
			return min(costs[0])
		elif k == 1:
			return -1
		dp = [[0 for _ in range(k)] for i in range(n)]
		for i in range(n):
			for j in range(k):
				dp[i][j] = costs[i][j]
		min_value = [[sys.maxsize for i in range(4)] for j in range(n)]
		for i in range(0, 1):
			for j in range(k):
				if min_value[i][0] > costs[i][j]:
					min_value[i][2] = min_value[i][0]
					min_value[i][3] = min_value[i][1]
					min_value[i][0] = costs[i][j]
					min_value[i][1] = j
				elif min_value[i][0] == costs[i][j]:
					min_value[i][2] = min_value[i][0]
					min_value[i][3] = j
				if min_value[i][2] > costs[i][j] and costs[i][j] > min_value[i][0]:
					min_value[i][2] = costs[i][j]
					min_value[i][3] = j
		result = sys.maxsize
		for i in range(1, n):
			for j in range(k):
				if min_value[i - 1][1] == j:
					dp[i][j] += min_value[i - 1][2]
				else:
					dp[i][j] += min_value[i - 1][0]
			for j in range(k):
				if min_value[i][0] > dp[i][j]:
					min_value[i][2] = min_value[i][0]
					min_value[i][3] = min_value[i][1]
					min_value[i][0] = dp[i][j]
					min_value[i][1] = j
				elif min_value[i][0] == dp[i][j]:
					min_value[i][2] = min_value[i][0]
					min_value[i][3] = j
				if min_value[i][2] > dp[i][j] and dp[i][j] > min_value[i][0]:
					min_value[i][2] = dp[i][j]
					min_value[i][3] = j
		result = min(dp[n - 1])
		return result


from typing import List

class Solution:

	def minCost(self, costs: List[List[int]]) -> int:
		(n, k) = (len(costs), len(costs[0]))
		if k < 2 and n > 1:
			return -1
		for i in range(1, n):
			cur = costs[i - 1][:]
			minm = min(cur)
			cur.remove(minm)
			sec_min = min(cur)
			for j in range(k):
				if costs[i - 1][j] == minm:
					costs[i][j] += sec_min
				else:
					costs[i][j] += minm
		return min(costs[-1])


from sortedcontainers import SortedList

class Solution:

	def minCost(self, costs) -> int:
		(N, K) = (len(costs), len(costs[0]))
		if N == 0:
			return 0
		if N == 1:
			return min(costs[0])
		if K == 0 or (N > 1 and K == 1):
			return -1
		for i in range(1, N):
			li = SortedList(costs[i - 1][:])
			(c1, c2) = (li[0], li[1])
			for j in range(K):
				if costs[i - 1][j] == c1:
					costs[i][j] += c2
				else:
					costs[i][j] += c1
		return min(costs[-1])


class Solution:

	def minCost(self, costs) -> int:
		import numpy as np
		(N, K) = (len(costs), len(costs[0]))
		if N <= 0 or K <= 0 or (K == 1 and N >= 2):
			return -1
		(dp, tmp) = (costs[0].copy(), [0] * K)
		for i in range(1, N):
			min1 = np.argmin(dp)
			min2 = min(((v, i) for (i, v) in enumerate(dp) if i != min1))[1]
			for j in range(K):
				tmp[j] = costs[i][j] + (dp[min1] if min1 != j else dp[min2])
			(dp, tmp) = (tmp, dp)
		return min(dp)


class Solution:

	def minCost(self, costs):
		N = len(costs)
		K = len(costs[0])
		if K <= 1 and N > 1:
			return -1
		if K == 1 and N == 1:
			return costs[0][0]
		dp = costs[0].copy()
		for i in range(1, N):
			a = sorted(dp)
			m = a[0]
			s = a[1]
			te = [0] * K
			for j in range(K):
				minn = m
				if minn == dp[j]:
					minn = s
				te[j] = costs[i][j] + minn
			dp = te
		return min(dp)


class Solution:

	def minCost(self, costs) -> int:
		(n, k) = (len(costs), len(costs[0]))
		dp = [[-1] * (k + 1) for _ in range(n + 1)]
		for i in range(k + 1):
			dp[0][i] = 0
		for i in range(1, n + 1):
			min1 = [float('inf'), -1]
			min2 = [float('inf'), -1]
			for j in range(k):
				if min1[0] > dp[i - 1][j] + costs[i - 1][j]:
					min2[0] = min1[0]
					min2[1] = min1[1]
					min1[0] = dp[i - 1][j] + costs[i - 1][j]
					min1[1] = j
				elif min2[0] > dp[i - 1][j] + costs[i - 1][j]:
					min2[0] = dp[i - 1][j] + costs[i - 1][j]
					min2[1] = j
			for prev in range(k + 1):
				if prev == min1[1]:
					dp[i][prev] = min2[0]
				else:
					dp[i][prev] = min1[0]
		res = dp[n][k]
		return res if res != float('inf') else -1


class Solution:

	def minCost(self, cost):
		n = len(cost)
		k = len(cost[0])
		if k == 1:
			if n == 1:
				return cost[0][0]
			return -1
		mini = [float('inf'), -1]
		smini = [float('inf'), -1]
		for i in range(k):
			if cost[0][i] < mini[0]:
				smini = mini
				mini = [cost[0][i], i]
			elif cost[0][i] < smini[0]:
				smini = [cost[0][i], i]
		for i in range(1, n):
			curMini = [float('inf'), -1]
			curSmini = [float('inf'), -1]
			for j in range(k):
				x = cost[i][j]
				if j != mini[1]:
					x += mini[0]
				else:
					x += smini[0]
				if x < curMini[0]:
					curSmini = curMini
					curMini = [x, j]
				elif x < curSmini[0]:
					curSmini = [x, j]
			mini = curMini
			smini = curSmini
		return mini[0]


class Solution:

	def minCost(self, costs) -> int:
		from heapq import heappushpop, heappush, heappop
		if len(costs) == 1:
			return min(costs[0])
		if len(costs[0]) == 1:
			return -1
		(n, k) = (len(costs), len(costs[0]))
		dp = [[0] * k for _ in range(n + 1)]
		(min1, min2) = ((0, None), (0, None))
		h = []
		for wall in range(n):
			for color in range(k):
				dp[wall + 1][color] = (min1[0] if min1[1] != color else min2[0]) + costs[wall][color]
				if len(h) < 2:
					heappush(h, (-dp[wall + 1][color], color))
				else:
					heappushpop(h, (-dp[wall + 1][color], color))
			min2 = heappop(h)
			min2 = (min2[0] * -1, min2[1])
			min1 = heappop(h)
			min1 = (min1[0] * -1, min1[1])
		return min1[0]
from typing import List

class IntMatrix:

	def __init__(self) -> None:
		pass

	def Input(self, n, m):
		matrix = []
		for _ in range(n):
			matrix.append([int(i) for i in input().strip().split()])
		return matrix

	def Print(self, arr):
		for i in arr:
			for j in i:
				print(j, end=' ')
			print()
if __name__ == '__main__':
	t = int(input())
	for _ in range(t):
		(n, m) = map(int, input().split())
		costs = IntMatrix().Input(n, m)
		obj = Solution()
		res = obj.minCost(costs)
		print(res)


import sys

class Solution:

	def recur(self, i, last, arr, dp):
		if i == 0:
			mini = sys.maxsize
			for l in range(0, len(arr[0])):
				if l != last:
					mini = min(mini, arr[i][l])
			return mini
		if dp[i][last] != -1:
			return dp[i][last]
		mini = sys.maxsize
		for l in range(0, len(arr[0])):
			if l != last:
				cost = arr[i][l] + self.recur(i - 1, l, arr, dp)
				mini = min(mini, cost)
		dp[i][last] = mini
		return mini

	def minCost(self, costs) -> int:
		import numpy as np
		(N, K) = (len(costs), len(costs[0]))
		if N <= 0 or K <= 0 or (K == 1 and N >= 2):
			return -1
		(dp, tmp) = (costs[0].copy(), [0] * K)
		for i in range(1, N):
			min1 = np.argmin(dp)
			min2 = min(((v, i) for (i, v) in enumerate(dp) if i != min1))[1]
			for j in range(K):
				tmp[j] = costs[i][j] + (dp[min1] if min1 != j else dp[min2])
			(dp, tmp) = (tmp, dp)
		return min(dp)


from typing import List

class Solution:

	def minCost(self, costs: List[List[int]]) -> int:
		n = len(costs)
		k = len(costs[0])
		if k == 1 and n != 1:
			return -1
		dp = [[-1] * k for i in range(n)]
		for i in range(k):
			dp[0][i] = costs[0][i]
		for i in range(1, n):
			minCost = float('inf')
			minIndex = -1
			for j in range(k):
				if dp[i - 1][j] < minCost:
					minCost = dp[i - 1][j]
					minIndex = j
			minCost2 = float('inf')
			for j in range(k):
				if j != minIndex and dp[i - 1][j] < minCost2:
					minCost2 = dp[i - 1][j]
			for j in range(k):
				if j == minIndex:
					dp[i][j] = minCost2 + costs[i][j]
				else:
					dp[i][j] = minCost + costs[i][j]
		ans = float('inf')
		for i in range(k):
			ans = min(ans, dp[n - 1][i])
		return ans