Alice likes to shop online. The main reason is that she gets a lot of discounts! There are M online shops from where she purchases her items. The prices of the same item vary in both the shops. She needs to buy N items in all. And each she can buy each item in any one of the shops. All the shops offer certain discounts. If she buys the i^{th} item in one shop, she gets a discount coupon for the i+1^{th} item in the same shop. But if she purchases the i+1^{th} item from a different shop, she cannot use the discount coupon.
For example, if she buys the i^{th} item in Shop j and gets a discount of X rupees. Let the price of i+1^{th} item be Y rupees in shop j and Z rupees in shop k. If she purchases the i+1^{th} item from shop j she can use the discount coupon and hence, will have to pay Y-X rupees. If she purchases the i+1^{th} item from shop k she cannot use the discount coupon and hence, will have to pay Z rupees.
Note: If the discount given is more than price of the item in the shop, i.e. if Y-X < 0, the item is given free but she does NOT get any money back.
Alice wants to spend as less as possible and wants your help. She starts buying from item 1 and goes on till item N in that order. Your task is simple. Tell her the least amount to spend to get all the N items.

------ Input: ------ 

First line of input contains a single integer T, the number of test cases.

Each test case starts with a line consisting of two space separated integers N & M.
The next N lines consist of M space separated integers each. The j^{th} number on the i^{th} line denotes the price of i^{th} item in the j^{th} shop.

The next N lines consist of M space separated integers each. The j^{th} number on the i^{th} line denotes the value of discount coupon given after purchasing i^{th} item in the j^{th} shop.

------ Output: ------ 

For each test case, output on a separate line the least amount that has to be spent to get all the N items.

------ Constraints: ------ 

1 ≤ T ≤ 10
2 ≤ N, M ≤ 100000
0 ≤ Prices, Discounts ≤ 1000000
1 ≤ T * N * M ≤ 1000000

------ Scoring: ------ 

You will be awarded 40 points for solving the problem correctly for M = 2.

Another 20 points for solving the problem correctly for M ≤ 100.

Remaining 40 points will be awarded for solving the problem correctly for M > 100.

----- Sample Input 1 ------ 
2
2 2
3 4
1 2
1 0
0 1
2 4
1 2 3 4
4 3 2 1
2 3 2 1
1 2 1 1
----- Sample Output 1 ------ 
3
2

Difficulty: HARD
Tags: Dynamic programming

Data structures

Mathematics
Skill types: Dynamic programming

Data structures

Starter code:

Solutions:
for i in range(int(input())):
	(N, M) = list(map(int, input().split(' ')))
	C = [list(map(int, input().split(' '))) for _ in range(N)]
	D = [list(map(int, input().split(' '))) for _ in range(N)]
	dp = [[0] * M for _ in range(N)]
	for j in range(M):
		dp[0][j] = C[0][j]
	min_value = min(dp[0])
	for i in range(1, N):
		for j in range(M):
			dp[i][j] = min(min_value + C[i][j], dp[i - 1][j] + max(0, C[i][j] - D[i - 1][j]))
		min_value = min(dp[i])
	print(min_value)


t = int(input())
for _ in range(t):
	(n, m) = map(int, input().split())
	cost = []
	for i in range(n):
		e = list(map(int, input().split()))
		cost.append(e)
	disc = []
	for i in range(n):
		e = list(map(int, input().split()))
		disc.append(e)
	dp = [[0] * m for i in range(n)]
	curmin = float('inf')
	for j in range(m):
		dp[0][j] = cost[0][j]
		curmin = min(curmin, dp[0][j])
	for i in range(1, n):
		for j in range(m):
			dp[i][j] = min(curmin + cost[i][j], dp[i - 1][j] + max(0, cost[i][j] - disc[i - 1][j]))
		curmin = float('inf')
		for j in range(m):
			curmin = min(dp[i][j], curmin)
	print(curmin)


global ans
t = int(input())
for _ in range(t):
	(n, m) = map(int, input().split())
	prices = []
	for i in range(n):
		prices.append(list(map(int, input().split())))
	dis = []
	for i in range(n):
		dis.append(list(map(int, input().split())))
	dp = [[0] * m for i in range(n)]
	curmin = float('inf')
	for j in range(m):
		dp[0][j] = prices[0][j]
		curmin = min(curmin, dp[0][j])
	for i in range(1, n):
		for j in range(m):
			dp[i][j] = min(curmin + prices[i][j], dp[i - 1][j] + max(0, prices[i][j] - dis[i - 1][j]))
		curmin = float('inf')
		for j in range(m):
			curmin = min(dp[i][j], curmin)
	print(curmin)


for _ in range(int(input())):
	(n, m) = map(int, input().split())
	prices = [list(map(int, input().split())) for i in range(n)]
	dis = [list(map(int, input().split())) for i in range(n)]
	prev = min(prices[0][:])
	for i in range(1, n):
		cur_min = float('inf')
		for j in range(m):
			prices[i][j] = min(prev + prices[i][j], prices[i - 1][j] + max(0, prices[i][j] - dis[i - 1][j]))
			cur_min = min(cur_min, prices[i][j])
		prev = max(cur_min, 0)
	print(min(prices[-1][:]))


def helper(item, shop, discount):
	if item == n:
		return 0
	elif dp[item][shop] != float('inf'):
		return dp[item][shop]
	else:
		for i in range(m):
			if shop == i:
				dp[item][shop] = min(dp[item][shop], prices[item][shop] - discount + helper(item + 1, shop, discounts[item][shop]))
			else:
				dp[item][shop] = min(dp[item][shop], prices[item][i] + helper(item + 1, i, discounts[item][i]))
		return dp[item][shop]
t = int(input())
while t:
	(n, m) = list(map(int, input().split()))
	prices = []
	for i in range(n):
		prices.append(list(map(int, input().split())))
	discounts = []
	for i in range(n):
		discounts.append(list(map(int, input().split())))
	dp = [[0 for i in range(m)] for j in range(n)]
	mn = float('inf')
	for j in range(m):
		dp[0][j] = prices[0][j]
		mn = min(mn, dp[0][j])
	for i in range(1, n):
		for j in range(m):
			dp[i][j] = min(mn + prices[i][j], dp[i - 1][j] + max(0, prices[i][j] - discounts[i - 1][j]))
		mn = min(dp[i])
	print(mn)
	t -= 1


from sys import stdin, stdout
from sys import maxsize

def solve():
	pass
test = 1
test = int(input())
for t in range(0, test):
	(n, m) = list(map(int, input().split()))
	brr = [list(map(int, input().split())) for i in range(n)]
	drr = [list(map(int, input().split())) for i in range(n)]
	dp = [[0] * m for j in range(n)]
	dp[0] = brr[0]
	for i in range(1, n):
		v1 = min(dp[i - 1])
		ind = dp[i - 1].index(v1)
		for j in range(m):
			if j != ind:
				dp[i][j] = min(v1 + brr[i][j], dp[i - 1][j] + max(0, brr[i][j] - drr[i - 1][j]))
			else:
				dp[i][j] = dp[i - 1][j] + max(0, brr[i][j] - drr[i - 1][j])
	print(min(dp[n - 1]))


t = int(input())
while t > 0:
	t -= 1
	(n, m) = map(int, input().split())
	mat = []
	for i in range(n):
		temp = list(map(int, input().split()))
		mat.append(temp)
	dis = []
	for i in range(n):
		dis.append(list(map(int, input().split())))
	for i in range(1, n):
		minPrev = min(mat[i - 1])
		for j in range(m):
			dp = max(0, mat[i][j] - dis[i - 1][j])
			mat[i][j] = min(mat[i - 1][j] + dp, mat[i][j] + minPrev)
	print(min(mat[n - 1]))


t = int(input())
for l in range(t):
	(n, m) = list(map(int, input().split()))
	price = [list(map(int, input().split())) for x in range(n)]
	discount = [list(map(int, input().split())) for x in range(n)]
	ans = [[0] * m for x in range(n)]
	for i in range(n):
		curr_min = 100000000000000
		for j in range(m):
			if i == 0:
				ans[i][j] = price[i][j]
			else:
				cost1 = price[i][j] + prev_min
				cost2 = max(0, price[i][j] - discount[i - 1][j]) + ans[i - 1][j]
				ans[i][j] = min(cost1, cost2)
			curr_min = min(ans[i][j], curr_min)
		prev_min = curr_min
	print(curr_min)


def main():
	test_case = int(input())
	for itr in range(test_case):
		(item, shop) = map(int, input().split())
		costMatrix = []
		discountMatrix = []
		for itr_s in range(item):
			costMatrix.append(list(map(int, input().split())))
		for itr_s in range(item):
			discountMatrix.append(list(map(int, input().split())))
		print(solve(shop, item, costMatrix, discountMatrix))

def solve(shop, item, costMatrix, discountMatrix):
	ans = -1
	for i in range(item):
		tempminval = -1
		for j in range(shop):
			if i == 0:
				costMatrix[i][j] = costMatrix[i][j]
			else:
				minval = costMatrix[i - 1][j] + discount(costMatrix[i][j], discountMatrix[i - 1][j])
				if j == 0:
					for it in range(shop):
						tempval = costMatrix[i - 1][it]
						if tempval < tempminval or tempminval == -1:
							tempminval = tempval
				minval = min(minval, costMatrix[i][j] + tempminval)
				costMatrix[i][j] = minval
			if i == item - 1:
				ans = costMatrix[i][j] if ans == -1 or ans > costMatrix[i][j] else ans
	return ans

def discount(cost, discount):
	return cost - discount if cost > discount else 0
main()


for t in range(int(input())):
	(n, m) = map(int, input().split(' '))
	prices = []
	discounts = []
	for i in range(n):
		price = list(map(int, input().split(' ')))
		prices.append(price)
	for i in range(n):
		discount = list(map(int, input().split(' ')))
		discounts.append(discount)
	table = [[0 for i in range(m)] for j in range(n)]
	for i in range(m):
		table[0][i] = prices[0][i]
	value = 0
	for i in range(1, n):
		value = min(table[i - 1])
		for j in range(m):
			temp = max(0, prices[i][j] - discounts[i - 1][j])
			table[i][j] = min(temp + table[i - 1][j], prices[i][j] + value)
	print(min(table[n - 1]))


t = int(input())
INF = 10 ** 20
while t > 0:
	(n, m) = map(int, input().split())
	(price, discount) = ([], [])
	for i in range(n):
		price.append([])
		discount.append([])
	for i in range(n):
		l = list(map(int, input().split()))
		price[i] = l
	for i in range(n):
		l = list(map(int, input().split()))
		discount[i] = l
	dp = [[0] * m] * n
	ans = min(price[0])
	for i in range(m):
		val = price[0][i]
		dp[0][i] = val
	for i in range(1, n):
		ans2 = INF
		for j in range(m):
			val = price[i][j] - discount[i - 1][j] if price[i][j] - discount[i - 1][j] >= 0 else 0
			dp[i][j] = min(dp[i - 1][j] + val, ans + price[i][j])
			ans2 = min(ans2, dp[i][j])
		ans = ans2
	M = dp[n - 1][0]
	for r in dp:
		x = min(r)
		M = min(x, M)
	print(M)
	t -= 1


t = int(input())
for T in range(t):
	(n, m) = [int(x) for x in input().split()]
	(cost, disc, dp) = ([], [], [])
	for i in range(n):
		cost.append([int(x) for x in input().split()])
	for i in range(n):
		disc.append([int(x) for x in input().split()])
	val = 0
	dp = [[0 for j in range(m)] for i in range(n)]
	for i in range(m):
		dp[0][i] = cost[0][i]
	for i in range(1, n):
		val = min(dp[i - 1])
		for j in range(m):
			v1 = max(0, cost[i][j] - disc[i - 1][j])
			dp[i][j] = min(dp[i - 1][j] + v1, val + cost[i][j])
	print(min(dp[n - 1]))


t = int(input())
for i in range(t):
	(n, m) = map(int, input().split())
	prices = []
	for j in range(n):
		arr = [int(k) for k in input().split()]
		prices += [arr]
	discounts = []
	for j in range(n):
		arr = [int(k) for k in input().split()]
		discounts += [arr]
	dp = [[[-1] * 2 for j in range(m)] for j in range(n)]
	mi = 10 ** 10
	prevmi = 10 ** 10
	prevprevmi = 10 ** 10
	for x in range(m):
		for z in range(2):
			dp[0][x][z] = prices[0][x]
			if prices[0][x] <= mi:
				prevprevmi = prevmi
				prevmi = mi
				mi = prices[0][x]
			elif prices[0][x] > mi and prices[0][x] <= prevmi:
				prevprevmi = prevmi
				prevmi = prices[0][x]
			elif prices[0][x] > prevmi and prices[0][x] <= prevprevmi:
				prevprevmi = prices[0][x]
	for x in range(1, n):
		mi2 = 10 ** 15
		prevmi2 = 10 ** 15
		prevprevmi2 = 10 ** 15
		for y in range(m):
			discprice = prices[x][y] - discounts[x - 1][y]
			if discprice < 0:
				discprice = 0
			dp[x][y][1] = min(dp[x - 1][y][0], dp[x - 1][y][1]) + discprice
			if dp[x][y][1] <= mi2:
				prevprevmi2 = prevmi2
				prevmi2 = mi2
				mi2 = dp[x][y][1]
			elif dp[x][y][1] > mi2 and dp[x][y][1] <= prevmi2:
				prevprevmi2 = prevmi2
				prevmi2 = dp[x][y][1]
			elif dp[x][y][1] > prevmi2 and dp[x][y][1] <= prevprevmi2:
				prevprevmi2 = dp[x][y][1]
			if sorted([dp[x - 1][y][0], dp[x - 1][y][1]]) == [mi, prevmi]:
				dp[x][y][0] = prevprevmi + prices[x][y]
			elif dp[x - 1][y][0] == mi or dp[x - 1][y][1] == mi:
				dp[x][y][0] = prevmi + prices[x][y]
			else:
				dp[x][y][0] = mi + prices[x][y]
			if dp[x][y][0] <= mi2:
				prevprevmi2 = prevmi2
				prevmi2 = mi2
				mi2 = dp[x][y][0]
			elif dp[x][y][0] > mi2 and dp[x][y][0] <= prevmi2:
				prevprevmi2 = prevmi2
				prevmi2 = dp[x][y][0]
			elif dp[x][y][0] > prevmi2 and dp[x][y][0] <= prevprevmi2:
				prevprevmi2 = dp[x][y][0]
		prevprevmi = prevprevmi2
		prevmi = prevmi2
		mi = mi2
	print(mi)


for _ in range(int(input())):
	(n, m) = map(int, input().split())
	cost = [list(map(int, input().split())) for i in range(n)]
	disc = [list(map(int, input().split())) for i in range(n)]
	dp = [[0 for j in range(m)] for i in range(n)]
	for i in range(m):
		dp[0][i] = cost[0][i]
	for i in range(1, n):
		prev = min(dp[i - 1])
		for j in range(m):
			d = max(0, cost[i][j] - disc[i - 1][j])
			dp[i][j] = min(dp[i - 1][j] + d, prev + cost[i][j])
	print(min(dp[n - 1]))


import sys
data = [int(i) for i in sys.stdin.read().split()]
data.reverse()

def read():
	return data.pop()
T = read()
for test in range(T):
	(n, m) = (read(), read())
	P = [[read() for j in range(m)] for i in range(n)]
	D = [[read() for j in range(m)] for i in range(n)]
	DP = [[[0 for k in range(2)] for j in range(m)] for i in range(n + 1)]
	mn = 0
	for i in range(n - 1, -1, -1):
		cnt = 10 ** 18
		for j in range(m):
			toAdd = min(mn, DP[i + 1][j][1])
			DP[i][j][0] = toAdd + P[i][j]
			if i:
				DP[i][j][1] = toAdd + max(0, P[i][j] - D[i - 1][j])
			cnt = min(cnt, DP[i][j][0])
		mn = cnt
	print(mn)


t = int(input())
for i in range(t):
	(n, m) = map(int, input().split())
	pri = [list(map(int, input().split())) for x in range(n)]
	dis = [list(map(int, input().split())) for x in range(n)]
	a = [[0] * m for x in range(n)]
	a[0] = pri[0][:]
	min1 = min(pri[0])
	for j in range(1, n):
		min2 = 10000000000000.0
		for k in range(m):
			di = max(0, pri[j][k] - dis[j - 1][k])
			a[j][k] = min(min1 + pri[j][k], a[j - 1][k] + di)
			min2 = min(min2, a[j][k])
		min1 = min2
	print(min(a[n - 1]))


t = int(input())
for _ in range(t):
	(n, m) = list(map(int, input().split(' ')))
	cst = list()
	for _ in range(n):
		cst.append(list(map(int, input().split(' '))))
	dsc = list()
	for _ in range(n):
		dsc.append(list(map(int, input().split(' '))))
	dp = list()
	dp.append(cst[0][:])
	for _ in range(n - 1):
		dp.append([0 for x in range(m)])
	for i in range(1, n):
		mn = min(dp[i - 1][:])
		for j in range(m):
			h = cst[i][j] - dsc[i - 1][j]
			if h < 0:
				h = 0
			dp[i][j] = min(mn + cst[i][j], dp[i - 1][j] + h)
	print(min(dp[n - 1][:]))


mod = 1000000007
inf = mod

def solve(n, m, dp, discounts, prices):
	prev = inf * inf
	for i in range(m):
		dp[0][i] = prices[0][i]
		prev = min(prev, dp[0][i])
	for i in range(1, n):
		prev2 = inf * inf
		for j in range(m):
			d = max(0, prices[i][j] - discounts[i - 1][j])
			dp[i][j] = dp[i - 1][j] + d
			dp[i][j] = min(dp[i][j], prev + prices[i][j])
			prev2 = min(prev2, dp[i][j])
		prev = prev2
	return min(dp[n - 1])
tests = int(input())
for _ in range(tests):
	(n, m) = map(int, input().split())
	prices = []
	dp = []
	discounts = []
	for i in range(n):
		temp = list(map(int, input().split()))
		temp2 = [0] * m
		dp.append(temp2)
		prices.append(temp)
	for i in range(n):
		temp = list(map(int, input().split()))
		discounts.append(temp)
	print(solve(n, m, dp, discounts, prices))