Given n arrays of size m each. Find maximum sum obtained by selecting a number from each array such that the element selected from the i-th array is more than the element selected from (i-1)-th array. If maximum sum cannot be obtained then return 0.
Example 1:
Ã¢â¬â¹Input : arr[ ] = {{1,7,4,3}, {4,2,5,1}, {9,5,1,8}}
Output : 18
Explanation:
We can select 4 from the first array,
5 from second array and 9 from the third array.
Ã¢â¬â¹Example 2:
Input : arr[ ] = {{9,8,7}, {6,5,4}, {3,2,1}} 
Output :  0
Your Task:
This is a function problem. The input is already taken care of by the driver code. You only need to complete the function maximumSum() that takes number of row N, a number of Column M, 2-d array (arr), and return the maximum sum if cannot be obtained then return 0. The driver code takes care of the printing.
Expected Time Complexity: O(N*M).
Expected Auxiliary Space: O(1).
 
Constraints:
1 ≤ N, M ≤ 500

Source: geeksforgeeks | Difficulty: EASY
Tags: Complete search

Data structures

Greedy algorithms

Starter code: #User function Template for python3



def maximumSum (n, m, arr) : 

    #Complete the function



Solutions:
def maximumSum(n, m, arr):
	try:
		a = arr
		for i in range(0, n):
			a[i].sort(reverse=True)
		for i in reversed(range(0, n - 1)):
			point = 0
			while a[i][0] >= a[i + 1][0]:
				a[i].pop(0)
				if len(a[i]) == 0:
					break
		ans = 0
		for i in range(0, n):
			if len(a[i]) == 0:
				ans = 0
				break
			ans += a[i][0]
		return ans
	except:
		return 0


def maximumSum(n, m, arr):
	total = max(arr[-1])
	n_max = total
	for i in range(n - 2, -1, -1):
		arr[i].sort(reverse=True)
		found = False
		for j in arr[i]:
			if j < n_max:
				n_max = j
				total += n_max
				found = True
				break
		if not found:
			return 0
	return total


def maximumSum(n, m, arr):
	sums = 0
	for i in range(len(arr)):
		arr[i].sort(reverse=True)
	arr = arr[::-1]
	max_val = 0
	for i in range(len(arr)):
		if i == 0:
			sums += arr[i][0]
			max_val = arr[i][0]
			continue
		j = 0
		while j < len(arr[i]) and arr[i][j] >= max_val:
			j += 1
		if j == len(arr[i]):
			return 0
		else:
			max_val = arr[i][j]
			sums += arr[i][j]
	return sums


def maximumSum(n, m, arr):

	def chapri(num, maxi):
		temp = -1
		for i in num:
			if temp < i < maxi:
				temp = i
		return temp
	a = max(arr[-1])
	b = a
	for i in range(2, n + 1):
		c = chapri(arr[-i], a)
		if c == -1:
			return 0
		else:
			(b, a) = (b + c, c)
	return b


def maximumSum(n, m, arr):
	s = max(arr[n - 1])
	sum = s
	q = 0
	for i in range(n - 2, -1, -1):
		p = sorted(arr[i], reverse=True)
		for k in p:
			if k < s:
				q = q + 1
				break
		s = k
		sum = sum + s
	if q == n - 1:
		return sum
	else:
		return 0


def maximumSum(n, m, arr):
	for i in range(n):
		arr[i].sort()
	s = arr[-1][-1]
	t = -1
	for i in range(n - 1, 0, -1):
		if arr[i][t] > arr[i - 1][0]:
			j = m - 1
			while j >= 0:
				if arr[i - 1][j] < arr[i][t]:
					s += arr[i - 1][j]
					t = j
					break
				j -= 1
		else:
			return 0
	return s


def maximumSum(n, m, arr):
	sumNM = 0
	prev = 1000000
	i = n - 1
	while i >= 0:
		maxm = -10000
		exists = 0
		for j in range(m):
			if arr[i][j] < prev:
				exists = 1
				if arr[i][j] > maxm:
					maxm = arr[i][j]
		if exists == 0:
			return 0
		prev = maxm
		sumNM += maxm
		i -= 1
	return sumNM


def maximumSum(n, m, arr):
	for i in range(n):
		arr[i].sort()
		summ = arr[n - 1][m - 1]
		end = m - 1
		start = arr[n - 1][m - 1]
	for i in range(n - 2, -1, -1):
		if arr[i][m - 1] < start:
			summ += arr[i][m - 1]
			start = arr[i][m - 1]
		else:
			while arr[i][end] >= start and end >= 0:
				end -= 1
			if end < 0:
				return 0
			else:
				summ += arr[i][end]
				start = arr[i][end]
				end = m - 1
	return summ


def maximumSum(n, m, arr):
	for i in range(n):
		arr[i].sort(reverse=True)
	max = arr[n - 1][0]
	count = arr[n - 1][0]
	for i in range(n - 2, -1, -1):
		for j in range(m):
			if max <= arr[i][j] and j == m - 1:
				return 0
			elif max > arr[i][j]:
				count += arr[i][j]
				max = arr[i][j]
				break
	return count


def maximumSum(n, m, arr):
	for i in range(n):
		arr[i].sort()
	summa = [arr[-1][-1]]
	for i in range(1, n):
		for j in range(m):
			if arr[-i - 1][-j - 1] < summa[-1]:
				summa.append(arr[-i - 1][-j - 1])
				break
	return 0 if len(summa) < n else sum(summa)


def maximumSum(n, m, arr):
	s = max(arr[-1])
	pre = max(arr[-1])
	for i in range(n - 2, -1, -1):
		num = -100000000
		for j in range(m):
			if arr[i][j] < pre and arr[i][j] > num:
				num = arr[i][j]
		if num == -100000000:
			return 0
		s += num
		pre = num
	return s


def maximumSum(n: int, m: int, arr: list) -> int:
	import math
	maximum = float('inf')
	result = 0
	for i in range(n - 1, -1, -1):
		max_value = float('-inf')
		for j in range(m):
			if arr[i][j] > max_value and arr[i][j] < maximum:
				max_value = arr[i][j]
		if math.isinf(max_value):
			return 0
		else:
			result += max_value
			maximum = max_value
	return result


def maximumSum(n, m, arr):
	sum = 0
	sum += max(arr[n - 1])
	for i in range(n - 2, -1, -1):
		jk = max(arr[i + 1])
		while True:
			if len(arr[i]) == 0:
				return 0
			pk = max(arr[i])
			if pk < jk:
				sum += pk
				break
			else:
				arr[i].remove(pk)
				continue
	return sum


def maximumSum(n, m, arr):
	for i in range(n):
		arr[i].sort()
	a = []
	max_ = arr[n - 1][m - 1]
	a.append(max_)
	for i in range(n - 2, -1, -1):
		j = m - 1
		while j >= 0:
			if arr[i][j] < max_:
				max_ = arr[i][j]
				a.append(max_)
				break
			else:
				j = j - 1
				if j == -1:
					return 0
	return sum(a)


def maximumSum(n, m, arr):
	sum = 0
	prev = 10000000
	for i in range(n - 1, -1, -1):
		arr[i].sort()
		j = m - 1
		while arr[i][j] >= prev and j >= 0:
			j -= 1
		if j < 0:
			return 0
		prev = arr[i][j]
		sum += prev
	return sum


def maximumSum(n, m, a):
	for i in range(n):
		a[i].sort()
	(c, k) = (a[n - 1][m - 1], a[n - 1][m - 1])
	for i in range(n - 2, -1, -1):
		t = a[i][m - 1]
		if t < k:
			c += t
			k = t
		else:
			for j in range(m - 1, -1, -1):
				t = a[i][j]
				if t < k:
					c += t
					k = t
					break
			else:
				return 0
	return c


def maximumSum(n, m, arr):
	ans = max(arr[n - 1])
	prev = ans
	for i in range(n - 2, -1, -1):
		max_ele = -1
		for a in arr[i]:
			if a < prev and max_ele < a:
				max_ele = a
		if max_ele == -1:
			return 0
		prev = max_ele
		ans += max_ele
	return ans


def maximumSum(n, m, arr):
	temp = []
	res = []
	for el in arr:
		temp.append(sorted(el, reverse=True))
	for i in range(len(temp) - 1, -1, -1):
		if i == len(temp) - 1:
			res.append(temp[i][0])
		else:
			flag = 0
			for el2 in temp[i]:
				if el2 < res[-1]:
					res.append(el2)
					flag = 1
					break
			if flag == 0:
				return 0
	return sum(res)


def maximumSum(n, m, arr):
	arr.reverse()
	k = max(arr[0])
	t = k
	for i in range(1, n):
		s = sorted(arr[i], reverse=True)
		if min(s) >= k:
			return 0
		for j in s:
			if k > j:
				k = j
				t = t + k
				break
	return t


def maximumSum(n, m, arr):
	last = n - 1
	first_max = -123456789
	for i in range(m):
		if arr[last][i] > first_max:
			first_max = arr[last][i]
	ans = first_max
	for i in range(n - 2, -1, -1):
		min_diff = 123456789
		val = None
		for j in range(m):
			if arr[i][j] < first_max and abs(first_max - arr[i][j]) < min_diff:
				min_diff = abs(first_max - arr[i][j])
				val = arr[i][j]
		if val == None:
			return 0
		ans += val
		first_max = val
	return ans


def maximumSum(n, m, arr):
	x = []
	arr = arr[::-1]
	x.append(max(arr[0]))
	c = max(arr[0])
	for i in arr[1:]:
		i.sort(reverse=True)
		for j in i:
			if j < c:
				x.append(j)
				c = j
				break
	if len(x) != len(arr):
		return 0
	return sum(x)


def maximumSum(n, m, arr):
	total = max(arr[-1])
	nmax = total
	for i in range(n - 2, -1, -1):
		arr[i].sort(reverse=True)
		found = False
		for j in arr[i]:
			if j < nmax:
				nmax = j
				total += nmax
				found = True
				break
		if not found:
			return 0
	return total
for _ in range(0, int(input())):
	(n, m) = map(int, input().split())
	arr = []
	for i in range(0, n):
		ll = list(map(int, input().strip().split()))
		arr.append(ll)
	ans = maximumSum(n, m, arr)
	print(ans)


import sys

def maximumSum(n, m, arr):
	qu = []
	for i in range(n - 1, -1, -1):
		maxm = -sys.maxsize
		for j in range(m):
			temp = sys.maxsize
			if len(qu):
				temp = qu[-1]
			if arr[i][j] > maxm and temp > arr[i][j]:
				maxm = arr[i][j]
		if maxm <= -sys.maxsize:
			return 0
		qu.append(maxm)
	return sum(qu)
for _ in range(0, int(input())):
	(n, m) = map(int, input().split())
	arr = []
	for i in range(0, n):
		ll = list(map(int, input().strip().split()))
		arr.append(ll)
	ans = maximumSum(n, m, arr)
	print(ans)


def maximumSum(n, m, a):
	for i in a:
		i.sort()
	sum1 = 0
	k = a[-1][m - 1]
	sum1 = k
	k1 = -1
	for i in range(n - 2, -1, -1):
		for j in range(m - 1, -1, -1):
			if a[i][j] < k:
				sum1 += a[i][j]
				k = a[i][j]
				k1 = 0
				break
		if k1 == -1:
			return 0
		k1 = -1
	return sum1


def maximumSum(n, m, arr):
	l1 = []
	for i in arr[::-1]:
		k = sorted(i)
		if len(l1) == 0:
			l1.append(k[-1])
		else:
			found = 0
			for j in k[::-1]:
				if j < l1[-1]:
					l1.append(j)
					found = 1
					break
			if found == 0:
				return 0
	return sum(l1)


def maximumSum(n, m, arr):
	mx = 100000000000000000
	s = 0
	for i in range(n - 1, -1, -1):
		arr[i].sort()
		fl = 0
		for j in range(m - 1, -1, -1):
			if arr[i][j] < mx:
				mx = arr[i][j]
				s += mx
				fl = 1
				break
		if fl == 0:
			return 0
	return s


def maximumSum(n, m, arr):
	limit = float('inf')
	sum = 0
	for i in range(n - 1, -1, -1):
		maxa = -1
		for j in range(m):
			if arr[i][j] < limit:
				maxa = max(maxa, arr[i][j])
		if maxa == -1:
			return 0
		limit = maxa
		sum += maxa
	return sum


def maximumSum(n, m, arr):
	prev = 9999
	sum = 0
	for i in range(n - 1, -1, -1):
		max_value = 0
		for j in range(m):
			if arr[i][j] < prev and arr[i][j] > max_value:
				max_value = arr[i][j]
		if max_value == 0:
			return 0
		else:
			prev = max_value
		sum = sum + prev
	return sum


def maximumSum(n, m, arr):
	sum = 0
	for i in range(n - 1, -1, -1):
		if i == n - 1:
			sum += max(arr[i])
			large = max(arr[i])
		else:
			count = 0
			for k in arr[i]:
				if k < large and k > count:
					count = k
			if count == 0:
				return 0
			else:
				large = count
				sum += large
	return sum


def maximumSum(n, m, arr):
	import sys
	tot = 0
	prev = max(arr[n - 1])
	tot += prev
	for i in range(n - 2, -1, -1):
		ref = arr[i]
		tmp = -sys.maxsize
		for v in ref:
			if v < prev:
				tmp = max(tmp, v)
		if tmp == -sys.maxsize:
			return 0
		else:
			tot += tmp
			prev = tmp
	return tot


def maximumSum(n, m, arr):
	for i in range(n):
		arr[i].sort(reverse=True)
	ans = arr[-1][0]
	premax = arr[-1][0]
	for i in range(n - 2, -1, -1):
		j = 0
		while j < m and arr[i][j] >= premax:
			j += 1
		if j == m:
			return 0
		ans += arr[i][j]
		premax = arr[i][j]
	return ans


def maximumSum(n, m, arr):
	ans = 0
	track = float('-inf')
	for i in range(len(arr) - 1, -1, -1):
		if i == len(arr) - 1:
			ans += max(arr[i])
			track = max(arr[i])
			continue
		else:
			ins = float('-inf')
			for k in arr[i]:
				if k > ins and k < track:
					ins = k
			if ins == float('-inf'):
				return 0
			else:
				ans += ins
				track = ins
	return ans


def maximumSum(n, m, arr):
	summ = 0
	prv_max = 9999999999999999999
	for i in range(n - 1, -1, -1):
		local_max = 0
		for j in range(0, m):
			if arr[i][j] > local_max and arr[i][j] < prv_max:
				local_max = arr[i][j]
		prv_max = local_max
		summ += local_max
		if local_max == 0:
			return 0
	return summ


def maximumSum(n, m, a):
	for arri in arr:
		arri.sort()
	prev = 100000000000.0
	Sum = 0
	for i in range(n - 1, -1, -1):
		for j in range(m - 1, -1, -1):
			if arr[i][j] < prev:
				Sum += arr[i][j]
				prev = arr[i][j]
				break
			if j == 0:
				return 0
	return Sum


def maximumSum(n, m, a):
	cur_max = 100000
	Final = []
	Flag = 1
	for i in reversed(arr):
		if Flag == 1:
			Final.append(max(i))
			Flag = 0
		else:
			maxm = 0
			for j in i:
				if j < Final[-1] and j > maxm:
					maxm = j
			if maxm == 0:
				return 0
			Final.append(maxm)
	return sum(Final)


def maximumSum(n, m, arr):
	arr.reverse()
	ans = []
	ans.append(max(arr[0]))
	for i in range(1, n):
		maxi = -1
		for el in arr[i]:
			if el < ans[-1] and el > maxi:
				maxi = el
		if maxi == -1:
			return 0
		ans.append(maxi)
	return sum(ans)


def maximumSum(n, m, arr):
	s = 0
	ans = 0
	for i in reversed(arr):
		if s == 0:
			ans += max(i)
			next = ans
			s = 1
		else:
			c = 0
			for j in i:
				if j < next:
					c = max(c, j)
			if c == 0:
				return 0
			ans += c
			next = c
	return ans


def maximumSum(n, m, arr):
	final = []
	flag = 1
	for i in reversed(arr):
		if flag == 1:
			final.append(max(i))
			flag = 0
		else:
			maxm = 0
			for j in i:
				if j < final[-1] and j > maxm:
					maxm = j
			if maxm == 0:
				return 0
			final.append(maxm)
	return sum(final)


def maximumSum(n, m, arr):
	val = max(arr[-1])
	max_sum = val
	if n == 1:
		return max_sum
	for i in range(n - 2, -1, -1):
		temp = min(arr[i])
		for j in range(0, m):
			if arr[i][j] >= temp and arr[i][j] < val:
				temp = arr[i][j]
		if temp < val:
			max_sum += temp
			val = temp
		else:
			return 0
	return max_sum


def maximumSum(n, m, arr):
	Sol = []
	temp = 1
	arr = reversed(arr)
	for i in arr:
		if temp == 1:
			Sol.append(max(i))
			temp = 0
		else:
			max_e = 0
			for j in i:
				if j < Sol[-1] and j > max_e:
					max_e = j
			if max_e == 0:
				return 0
			Sol.append(max_e)
	return sum(Sol)


def maximumSum(n, m, arr):
	for i in range(n):
		arr[i].sort()
	Sum = 0
	prevMax = 100000000000.0
	for i in range(n - 1, -1, -1):
		for j in range(m - 1, -1, -1):
			if arr[i][j] < prevMax:
				Sum += arr[i][j]
				prevMax = arr[i][j]
				break
			if j <= 0:
				return 0
	return Sum


def maximumSum(n, m, arr):
	ans = []
	flag = 1
	for i in reversed(arr):
		if flag == 1:
			ans.append(max(i))
			flag = 0
		else:
			mx = 0
			for j in i:
				if j < ans[-1] and j > mx:
					mx = j
			if mx == 0:
				return 0
			ans.append(mx)
	return sum(ans)


import sys

def maximumSum(n, m, arr):
	res = 0
	mini = sys.maxsize
	for i in range(n - 1, -1, -1):
		flag = False
		maxi = -999999999999999999
		for j in range(m):
			if mini > arr[i][j]:
				flag = True
				maxi = max(maxi, arr[i][j])
		mini = maxi
		res += maxi
		if not flag:
			return 0
	return res


import sys

def maximumSum(n, m, a):
	maxi = max(a[n - 1])
	sum = maxi
	for i in range(n - 2, -1, -1):
		j = m
		while j > 0:
			ele = max(a[i])
			if ele < maxi:
				maxi = ele
				sum += maxi
				break
			else:
				a[i].remove(ele)
				j -= 1
		else:
			sum = 0
			break
	return sum


def maximumSum(n, m, arr):
	sum = 0
	gmax = max(arr[n - 1])
	sum = gmax
	for i in range(n - 2, -1, -1):
		cmax = -10 ** 9
		for k in arr[i]:
			if k > cmax and k < gmax:
				cmax = k
		if cmax == -10 ** 9:
			return 0
		else:
			gmax = cmax
			sum = sum + gmax
	return sum


def maximumSum(n, m, arr):
	sum = 0
	maxi = max(arr[n - 1])
	for i in range(n - 2, -1, -1):
		max1 = maxi
		sum += max1
		arr[i].sort()
		for i in arr[i][::-1]:
			if i < maxi:
				maxi = i
				break
		if maxi == max1:
			return 0
	return sum + maxi


def maximumSum(n, m, arr):
	ans = 0
	lastm = -10000000
	for i in range(m):
		lastm = max(lastm, arr[n - 1][i])
	ans += lastm
	for i in reversed(range(n - 1)):
		maxi = -10000000
		flag = 0
		for j in range(m):
			if arr[i][j] < lastm:
				flag = 1
				maxi = max(arr[i][j], maxi)
		if flag == 0:
			return 0
		ans += maxi
		lastm = maxi
	return ans


def maximumSum(n, m, arr):
	SumList = [max(arr[-1])]
	for i in range(n - 1):
		t = 0
		for j in arr[n - 2 - i]:
			if j < SumList[-1] and j > t:
				t = j
		if t == 0:
			return 0
		SumList.append(t)
	return sum(SumList)


def maximumSum(n, m, arr):
	arr = arr[::-1]
	m = int(max(arr[0]))
	sum = m
	for i in range(1, n):
		M = 0
		for j in arr[i]:
			if m > int(j) and int(j) > M:
				M = int(j)
		sum += int(M)
		m = int(M)
		if M == 0:
			return 0
	return sum


def maximumSum(n, m, arr):
	largest_numbers = []
	for array_index in range(n - 1, -1, -1):
		current_array = arr[array_index]
		if len(largest_numbers) == 0:
			largest_numbers.append(max(current_array))
		else:
			current_array = [num for num in current_array if num < min(largest_numbers)]
			if len(current_array) > 0:
				largest_numbers.append(max(current_array))
			else:
				return 0
	return sum(largest_numbers)


import sys

def maxi(a, n, limit):
	mini = -1
	for i in range(0, n):
		if a[i] > mini and a[i] < limit:
			mini = a[i]
	if mini < limit:
		return mini
	return -1

def maximumSum(n, m, arr):
	curr = 0
	limit = max(arr[n - 1])
	sumi = limit
	for i in range(n - 2, -1, -1):
		a = maxi(arr[i], m, limit)
		limit = a
		if a == -1:
			return 0
		sumi = sumi + a
	return sumi


def maximumSum(n, m, arr):
	s = 0
	m = max(arr[n - 1])
	s = m
	for i in range(len(arr) - 2, -1, -1):
		k = max(arr[i])
		if k < m:
			s = s + k
			m = k
		else:
			k = 0
			for j in arr[i]:
				if j < m and j > k:
					k = j
			if k == 0:
				return 0
			s = s + k
			m = k
	return s


def maximumSum(n, m, arr):
	mx = max(arr[-1])
	sm = mx
	for i in range(n - 2, -1, -1):
		this = -99999
		for j in range(m):
			if arr[i][j] > this and arr[i][j] < mx:
				this = arr[i][j]
		if this == -99999:
			return 0
		else:
			sm += this
			mx = this
	return sm


def maximumSum(n, m, arr):
	maxx = max(arr[-1])
	ans = maxx
	for i in range(len(arr) - 2, -1, -1):
		big = 0
		for k in arr[i]:
			if k > big and k < maxx:
				big = k
		ans += big
		maxx = big
		if big == 0:
			return '0'
	return ans


def maximumSum(n, m, arr):
	ans = 0
	mx = float('inf')
	pre_mx = mx
	for i in range(len(arr) - 1, -1, -1):
		arr[i].sort(reverse=True)
		for j in range(len(arr[i])):
			if arr[i][j] < mx:
				ans += arr[i][j]
				mx = arr[i][j]
				break
		if pre_mx == mx:
			return 0
		else:
			pre_mx = mx
	return ans


def maximumSum(n, m, arr):
	arr = arr[::-1]
	currmax = max(arr[0])
	total = currmax
	for block in arr[1:]:
		try:
			nxt = max((i for i in block if i < currmax))
			total += nxt
			currmax = nxt
		except ValueError:
			return 0
	return total


def maximumSum(n, m, arr):
	l = []
	k = 9999999
	g = 0
	for i in arr[::-1]:
		h = -9999999
		for j in i:
			if j < k and j > h:
				h = j
		if h == -9999999:
			g = 1
			break
		k = h
		l.append(h)
	if g == 1:
		return 0
	else:
		return sum(l)


def maximumSum(n, m, arr):
	limit = max(arr[n - 1])
	ans = limit
	for row in range(n - 2, -1, -1):
		max_in_limit = float('-inf')
		for col in range(m - 1, -1, -1):
			if arr[row][col] < limit:
				max_in_limit = max(max_in_limit, arr[row][col])
		if max_in_limit == float('-inf'):
			return 0
		ans += max_in_limit
		limit = max_in_limit
	return ans


def maximumSum(n, m, arr):
	maxx = max(arr[-1])
	L = maxx
	for i in range(n - 2, -1, -1):
		temp = arr[i][0]
		for j in range(1, m):
			if max(temp, arr[i][j]) < maxx:
				temp = max(temp, arr[i][j])
			else:
				temp = min(temp, arr[i][j])
		if temp >= maxx:
			return 0
		else:
			maxx = temp
			L += maxx
	return L


import math

def maximumSum(n, m, arr):
	ans = 0
	prev_max = math.inf
	for i in range(len(arr) - 1, -1, -1):
		curr_max = -1
		for j in range(len(arr[i])):
			if arr[i][j] < prev_max:
				curr_max = max(curr_max, arr[i][j])
		if curr_max == -1:
			return 0
		prev_max = curr_max
		ans += curr_max
	return ans


import math

def maximumSum(n, m, arr):
	prev = math.inf
	total = 0
	for i in range(len(arr) - 1, -1, -1):
		flag = False
		for e in sorted(arr[i], reverse=True):
			if e < prev:
				prev = e
				total += e
				flag = True
				break
		if not flag:
			return 0
	return total


def maximumSum(n, m, arr):
	for i in range(n):
		arr[i].sort(reverse=True)
	(s, m) = (arr[-1][0], arr[-1][0])
	for i in range(n - 2, -1, -1):
		flag = 0
		for j in range(len(arr[i])):
			if arr[i][j] < m:
				s = s + arr[i][j]
				m = arr[i][j]
				flag = 1
				break
		if flag == 0:
			return 0
	return s


def maximumSum(n, m, arr):
	m = 0
	s = max(arr[n - 1])
	for i in range(n - 1, 0, -1):
		if i == n - 1:
			mi = max(arr[i])
		p = 0
		g = max(arr[i])
		for j in arr[i - 1]:
			if j >= mi:
				continue
			else:
				p = 1
				diff = mi - j
				if diff < g:
					h = j
					g = diff
		if p == 0:
			return 0
		s = s + h
		mi = h
	return s


def maximumSum(n, m, arr):
	sum = 0
	ele = 501
	for i in range(n - 1, -1, -1):
		flag = 0
		if max(arr[i]) < ele:
			ele = max(arr[i])
			sum += ele
		else:
			arr[i].sort()
			for j in range(m - 1, -1, -1):
				if arr[i][j] < ele:
					ele = arr[i][j]
					sum += ele
					flag = 1
					break
			if flag == 0:
				return 0
	return sum


def maximumSum(n, m, arr):
	su = 0
	prev = float('inf')
	for i in range(n - 1, -1, -1):
		ma = float('-inf')
		for j in range(m - 1, -1, -1):
			if arr[i][j] < prev:
				ma = max(arr[i][j], ma)
		if ma == float('-inf'):
			return 0
		su = su + ma
		prev = ma
	return su


def maximumSum(n, m, arr):
	ma = max(arr[-1])
	res = ma
	for i in range(n - 2, -1, -1):
		mi = 0
		f = 0
		for j in range(m):
			if arr[i][j] > mi and arr[i][j] < ma:
				mi = arr[i][j]
				f = 1
		res += mi
		ma = mi
		if f == 0:
			return 0
	return res


def maximumSum(n, m, arr):
	ans = max(arr[-1])
	m = max(arr[-1])
	for i in range(n - 2, -1, -1):
		l = arr[i].copy()
		l.sort()
		l.reverse()
		c = 0
		for j in l:
			if j < m:
				m = j
				ans = ans + j
				c = 1
				break
		if c == 0:
			return 0
	o = ans
	return o


def maximumSum(n, m, arr):
	maxi = max(arr[n - 1])
	maxSum = maxi
	i = n - 2
	while i >= 0:
		j = 0
		nmaxi = -1
		while j < m:
			if arr[i][j] > nmaxi and arr[i][j] < maxi:
				nmaxi = arr[i][j]
			j += 1
		if nmaxi == -1:
			return 0
		maxi = nmaxi
		maxSum += maxi
		i -= 1
	return maxSum


def maximumSum(n, m, arr):
	sol = max(arr[-1])
	cur_max = max(arr[-1])
	if n == 1:
		return cur_max
	for i in range(n - 2, -1, -1):
		ans = []
		for j in range(m):
			if arr[i][j] < cur_max:
				ans.append(arr[i][j])
		if ans:
			cur_max = max(ans)
			sol += cur_max
		else:
			return 0
	return sol


import sys

def maximumSum(n, m, arr):
	for i in arr:
		i.sort()
	ans = 0
	val = arr[n - 1][-1]
	sum = val
	for i in range(n - 2, -1, -1):
		temp = -sys.maxsize
		for j in range(m - 1, -1, -1):
			if arr[i][j] < val:
				temp = max(temp, arr[i][j])
		val = temp
		sum += temp
	return max(ans, sum)


def maximumSum(n, m, arr):
	if n == 1:
		return max(arr[0])
	revarr = arr[:]
	revarr.reverse()
	for i in range(n):
		revarr[i].sort(reverse=True)
	maxele = revarr[0][0]
	maxsum = maxele
	for i in range(1, n):
		flag = False
		for j in range(m):
			if revarr[i][j] < maxele:
				maxsum += revarr[i][j]
				maxele = revarr[i][j]
				flag = True
				break
		if flag == False:
			return 0
	return maxsum


import sys

def maximumSum(n, m, arr):
	arr.reverse()
	currmax = sys.maxsize
	summ = 0
	for i in arr:
		valarr = list(filter(lambda a: a < currmax, i))
		if len(valarr) == 0:
			return 0
		else:
			summ += max(valarr)
			currmax = max(valarr)
	return summ


def maximumSum(n, m, arr):
	if n == 1:
		return max(arr[0])
	a = max(arr[n - 1])
	s = a
	for i in range(n - 2, -1, -1):
		arr[i].sort()
		flag = 0
		for j in range(m - 1, -1, -1):
			if arr[i][j] < a:
				a = arr[i][j]
				flag = 1
				s = s + a
				break
		if flag == 0:
			return 0
	return s


def findMax(a, p):
	while len(a) != 0:
		m = max(a)
		if m < p:
			return m
		del a[a.index(m)]
	return -1

def maximumSum(n, m, arr):
	maxSum = prev = max(arr[n - 1])
	i = n - 2
	while i >= 0:
		curr = findMax(arr[i], prev)
		if curr == -1:
			return 0
		maxSum += curr
		prev = curr
		i -= 1
	return maxSum


def maximumSum(n, m, arr):
	x = arr[n - 1]
	x.sort(reverse=True)
	maxValue = x[0]
	sumValue = maxValue
	for i in range(n - 2, -1, -1):
		localMax = -1
		flag = False
		for j in range(m):
			if arr[i][j] < maxValue and arr[i][j] > localMax:
				localMax = arr[i][j]
				flag = True
		if not flag:
			return 0
		maxValue = localMax
		sumValue += localMax
	return sumValue


from sys import maxsize

def maximumSum(n, m, arr):
	sum = 0
	pme = maxsize
	arr.reverse()
	for i in arr:
		z = len(i)
		for j in range(z):
			me = max(i)
			if me >= pme and len(i) > 0:
				i.remove(me)
				continue
			else:
				pme = me
				sum += me
				break
		if len(i) == 0:
			return 0
	return sum


def maximumSum(n, m, a):
	summed = 0
	max_val = max(a[len(a) - 1])
	summed += max_val
	counter = 1
	for i in range(len(a) - 2, -1, -1):
		flag = False
		temp_min_max = 0
		for j in range(len(a[i])):
			if a[i][j] < max_val and temp_min_max < a[i][j]:
				flag = True
				temp_min_max = max(temp_min_max, a[i][j])
		if flag:
			counter += 1
		summed += temp_min_max
		max_val = temp_min_max
	if counter == len(a):
		return summed
	else:
		return 0