Colored Array

All submissions for this problem are available.
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 spaceseparated 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 spaceseparated 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 jth 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
Example
Input: 1 4 2 1 1 1 2 2 1 1 1 1 1 1 3 1 0 1 0 1 1 0 1 0 Output: 5
Explanation:
For this sample, we can repaint only once, since K = 1. We should repaint 4^{th} cell with color 1. We will pay 1 for this, and receive:
1 (1^{st} cell  1^{st} color) +
1 (2^{nd} cell 1^{st} color) +
1 (3^{rd} cell  2^{nd} color) +
3 (4^{th} cell  1^{st} color) = 6.
Hence we get 6 − 1 = 5 points in total, and it is the optimal answer.
Author:  berezin 
Tester:  gerald 
Editorial  http://discuss.codechef.com/problems/COLARR 
Tags  berezin, easy, feb14 
Date Added:  7012014 
Time Limit:  2 sec 
Source Limit:  50000 Bytes 
Languages:  C, CPP14, JAVA, PYTH, PYTH 3.6, CS2, PAS fpc, PAS gpc, RUBY, PHP, GO, NODEJS, HASK, SCALA, D, PERL, FORT, WSPC, ADA, CAML, ICK, BF, ASM, CLPS, PRLG, ICON, SCM qobi, PIKE, ST, NICE, LUA, BASH, NEM, LISP sbcl, LISP clisp, SCM guile, JS, ERL, TCL, PERL6, TEXT, CLOJ, FS 
Comments
 Please login at the top to post a comment.
SUCCESSFUL SUBMISSIONS
Fetching successful submissions