2016 ACM ICPC Asia Nha Trang Regional Contest Replay

Start

2017-10-15 12:00 UTC

2016 ACM ICPC Asia Nha Trang Regional Contest Replay

End

2017-10-15 17:00 UTC
The end is near!
Contest is over.
Not yet started.
Contest is starting in -427 days 12:35:59

Time elapsed

5:00:00

Time remaining

0:00:00

Problem L
Olympiad Training

Beside the pretigious ACM-ICPC contest, Nha Trang University also hosted the Vietnamese Collegiate Olympiads in Informatics 2016. This Olympiad has 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}^{th}$ student will require ${a}_{i,j}$ minutes to understand the ${j}^{th}$ topic. Teaching $K$ students ${X}_{1}, {X}_{2},..., {X}_{k}$ the ${j}^{th}$ topic will require $max({a}_{{x}_{k,j}}, {a}_{{x}_{2,j}},..., {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}},..., {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 10000)$.

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

  • The ${u}^{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, write out $Q$ lines where the ${i}^{th}$ line contains the minimal time required for the ${i}^{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