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.
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.
For each dataset, output $Q$ lines where the ${i}^\textrm {th}$ line contains the minimal time required for the ${i}^\textrm {th}$ query.
Sample Input 1 | Sample Output 1 |
---|---|
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 |