Problem L
Olympiad Training

Besides the prestigious ACM-ICPC contest, Nha Trang University also hosted the Vietnamese Collegiate Olympiads in Informatics 2016. This Olympiad had several events where students compete individually to show their skills and knowledge.

After a successful contest this year, $N$ junior students in Nha Trang University expressed their interests to join the team next year to represent their university. But in order for them to be at a medal contender level, the coach, Mr. Van, has to teach them $M$ topics. The ${i}^\textrm {th}$ student will require ${a}_{i,j}$ minutes to understand the ${j}^\textrm {th}$ topic. Teaching $K$ students ${X}_{1}, {X}_{2},\ldots , {X}_{k}$ the ${j}^\textrm {th}$ topic will require $max({a}_{{x}_{k,j}}, {a}_{{x}_{2,j}},\ldots , {a}_{{x}_{k,j}})$ minutes and teaching them all $M$ topics will require $\sum _{j=1}^{M} max({a}_{{x}_{1,j}}, {a}_{{x}_{2,j}},\ldots , {a}_{{x}_{k,j}})$ minutes.

Given $K$ - the number of students in a group to train, your task is to help Mr. Van decide who he should pick in order to minimize the total time he needs to teach them all $M$ topics.

Input

The input consists of several datasets. The first line of the input contains the number of datasets which is a positive integer and is not greater than $100$. The following lines describe the datasets.

Each dataset is described by the following lines:

• The first line contains three integers $N, M, Q$ $(1 \leq Q \leq N \leq 20, M \leq 10\, 000)$.

• The ${i}^\textrm {th}$ line of the next $N$ lines contains $M$ integers ${a}_{i,j}$ $(0 \leq {a}_{i,j} \leq {10}^{9})$.

• The ${u}^\textrm {th}$ line of the next $Q$ lines contains a query which is an integer $K$ $(1 \leq K \leq N)$ representing the number of students in the group that Mr. Van needs to train.

Output

For each dataset, output $Q$ lines where the ${i}^\textrm {th}$ line contains the minimal time required for the ${i}^\textrm {th}$ query.

2
2 2 1
1 3
3 2
1
3 3 3
1 4 9
2 6 3
3 5 5
1
2
3

4
11
14
18