Read problems statements in Mandarin Chinese  and Russian. 
Chef had a hard time arguing with his friend, and after getting a great old kick Chef saw a colored array with N cells, numbered from 1 to N.  
The kick was so strong that Chef suddenly understood the rules of the game. 
Each cell is painted with a color. Here the colors are numbered from 1 to M.
For any cell i, Chef can repaint it with any color q, and the cost of such operation is C_{i,q} points.
However Chef can do at most K repaintings (0 repaintings is possible). 
After performing all repaintings, each cell will have some color. For each cell i, if cell i has color q then Chef will receive B_{i,q} points.
Now Chef is wondering how many points can he receive in total when he repaints optimally.

------ Input ------ 

The first line of the input contains an integer T, denoting the number of test cases. The description of T test cases follows.
The first line of each test case contains three space-separated integers N, M and K, denoting the number of cells and the number of colors, the maximal possible number of repaintings respectively. The next line contains N space-separated integers A_{1}, A_{2}, ..., A_{N}, denoting the initial colors of the cells. Then N lines follow. The i^{th} line of them contains M integers B_{i}_{1}, B_{i}_{2}, ..., B_{i}_{M}, where B_{ij} denotes how many points Chef will receive if the cell i will be painted with j-th color after all operations. Then N lines follow. The i^{th} line  of them contains M integers C_{i}_{1}, C_{i}_{2}, ..., C_{i}_{M}, where C_{ij} denotes how many points Chef will lose if he repaints the cell i with color j.

Note: Be careful that the size of input files can be large.

------ Output ------ 

For each test case, output a single line containing the maximal possible points.

------ Constraints ------ 

$1 ≤ T ≤ 5$
$0 ≤ K ≤ 1000$
$1 ≤ N, M ≤ 1000$
$1 ≤ A_{i} ≤ M$ 
$0 ≤ B_{i,j} ≤ 1000$
$0 ≤ C_{i,j} ≤ 1000$
$If j = A_{i}, then C_{i,j} = 0$

----- Sample Input 1 ------ 
1
4 2 1
1 1 2 2
1 1
1 1
1 1
3 1
0 1
0 1
1 0
1 0
----- Sample Output 1 ------ 
5
----- explanation 1 ------ 
For this sample, we can repaint only once, since K = 1. We should repaint 4th cell with color 1. We will pay 1 for this, and receive: 
1 (1st cell - 1st color) + 1 (2nd cell -1st color) + 1 (3rd cell - 2nd color) + 3 (4th cell - 1st color)  = 6.
Hence we get 6 ? 1 = 5 points in total, and it is the optimal answer.

Source: codechef | Difficulty: MEDIUM_HARD
Tags: Sorting

Constructive algorithms

Ad-hoc


Solutions:
t = int(input())
for i in range(t):
	(n, m, k) = map(int, input().split())
	a = list(map(int, input().split()))
	b = []
	for j in range(n):
		e = list(map(int, input().split()))
		b.append(e)
	c = []
	for z in range(n):
		e = list(map(int, input().split()))
		c.append(e)
	p = [0] * n
	g = [0] * n
	s = 0
	for v in range(n):
		p[v] = b[v][a[v] - 1]
		s += p[v]
		x = 0
		for u in range(m):
			e = b[v][u] - c[v][u] - p[v]
			x = max(x, e)
		g[v] = x
	g.sort()
	g.reverse()
	print(s + sum(g[:k]))


t = int(input())
for i in range(t):
	(n, m, k) = input().split()
	n = int(n)
	m = int(m)
	k = int(k)
	a = list(map(int, input().split()))
	b = list()
	for j in range(n):
		temp = list(map(int, input().split()))
		b.append(temp)
	c = list()
	for j in range(n):
		temp = list(map(int, input().split()))
		c.append(temp)
	cost = [0] * n
	max_gain = [0] * n
	sum1 = 0
	for j in range(n):
		cost[j] = b[j][a[j] - 1]
		sum1 = sum1 + cost[j]
		mp = 0
		for z in range(m):
			temp = b[j][z] - c[j][z] - cost[j]
			mp = max(mp, temp)
		max_gain[j] = mp
	max_gain.sort()
	max_gain.reverse()
	print(sum1 + sum(max_gain[:k]))