Rescue Cricketer

★★★★★

0 votes

Brute Force, Flow, Medium-Hard

Details

Input format

First line contains single integer T representing number of test cases.
Each test case starts with three space separated integers, N, L and K.
Next line contains N space separated integers, $i_{th}$ of which denotes $A_i$ .
Next line contains N space separated integers, $i_{th}$ of which denotes $B_i$ .
Next L lines contains L space separated integers, $j_{th}$ integer in the $i_{th}$ line denotes $W[i][j]$ .

Output format

For each test case, print the required answer in a single line. If it's impossible to convert array A into array B, print 1 instead.

Constraints

$1 \leq T \leq 5$
$1 \leq N \leq 10^5$
$1 \leq L \leq 100$
$0 \leq K \leq 10^4$
$1 \leq W[i][j] \leq 10^4$ for $i \ne j$
$W[i][i] = 0$

Subtask	Points
$1 \leq N, L, K \leq 8$	$10\%$
$W[i][j] = 1 \ \forall \ i, j \in [1, L]$ and $i \ne j$ $K = N$	$20\%$
Original Constraints	$70\%$

Sample Input

Sample Output

0
2

Time Limit: 2

Memory Limit: 256

Source Limit:

Explanation

For the first test case, swap $A_2$ and $A_3$ with 0 cost. So the answer is 0.

For the second test case, we need to change $A_1$ to 2, first change $A_1$ to 3 with cost 1 ( $W[1][3]$ , now you cannot use $W[1][2]$ and $W[1][1]$ and $W[1][3]$ as $K = 1$ ) and then change $A_1$ to 2 with cost 1 ( $W[3][2]$ , now you cannot use cost $W[3][1]$ and $W[3][2]$ and $W[3][3]$ as $K = 1$ ). So the minimum cost required is 2.