Succession

Interview

Time limit12sMemory limit1024 MB

Summary

Pick exactly K areas that form a connected subtree of the road tree to maximize total value, then count the ways to achieve that maximum modulo 1000000007.

Level: Medium6 of 10
Topics: Dynamic programming, Tree, DFS
Solved: No attempts yet

Problem

Vito ran many businesses in different areas of New York, from simple olive oil to more dangerous products. Competition was literally cut-throat, and Vito was most vulnerable while traveling. So he had some of the roads he used sanitized, so that he could travel between any two of his areas using only sanitized roads. Sanitization was extremely costly, so his Consigliere sanitized the minimum number of roads needed.

Vito grew old and handed the reins to his son Michael. The Capos wanted a part of the business too, so Michael will pick exactly $K$ areas for himself, and the Capos keep the rest. Michael worked out the business value of each area, including some loss-making areas. He wants to pick his $K$ areas so that the total business value is maximized and he can travel between any two of his areas using only sanitized roads. He also does not want to pass through an area that is not his. In other words, the chosen areas must form a connected part of the road network.

Find the highest possible total business value. Also find the number of ways to achieve it, modulo 1000000007.

Input

The first line contains $T$ , the number of test cases. The first line of each test case contains three space-separated integers $N$ , $K$ , and $R$ , where $N$ is the number of areas, $K$ is the number of areas Michael picks, and $R$ is the number of sanitized roads. The next line contains $N$ integers, where the $i$ -th integer is the business value of area $i$ . Each of the next $R$ lines contains two space-separated integers from and to (both 0-based), meaning there is a two-way sanitized road between areas from and to.

Output

For each test case, print one line with two space-separated integers. The first is the highest possible business value. The second is the number of ways to achieve it, modulo 1000000007.

Constraints

$1 \le T \le 100$
$1 \le K \le N \le 100$
Each business value is between $-1000$ and $1000$ , inclusive.
$0 \le from, to < N$ , and $from$ and $to$ are distinct.
No two roads connect the same pair of areas.
The roads connect every pair of areas, and removing any single road disconnects some pair of areas.

Examples1

Example 1
Input
```
1
2 1 1
10 10
0 1
```
Expected output
```
10 2
```