404687: GYM101608 K Running Threads

You're participating in a contest for finding the 10^31415926th prime number. You've developed a relatively fast algorithm, that has been working for a month, to find that number. To maximize the utilization of the resources you have, you distributed the work of the algorithm over k threads, where each thread was assigned a specific amount of work.

Two days left until the contest deadline, and the only thing you know about the progress of your algorithm is shown on the console window:

The first line shows the amount of work assigned to each of the k threads, these amounts were assigned randomly (clever!). Each of the following lines has a single integer that represents the current progress of one of the threads. You don't know for which thread each line belongs, but you do know that the progress value of each thread never decreases and doesn't exceed the amount of work assigned to the thread. Each thread takes a non-zero amount of the remaining work assigned to it, finishes it and then reports its new progress, for that no thread will print the same progress value twice, and all the finished work of the threads is reported.

To have an idea about the actual progress of your algorithm, you want to know the minimum and the maximum possible overall amount of remaining work.

The first line of input contains a single integer T, the number of test cases.

The first line of each test case contains two space-separated integers n and k (1 ≤ n ≤ 100) (2 ≤ k ≤ 16), the number of lines that shows progress values on your screen, and the number of threads.

The second line contains k space-separated integers w₁, w₂, ..., w_k (1 ≤ w_i ≤ 10⁹), the i^th integer represents the amount of work assigned to the i^th thread.

Each of the following n lines contains a single integer that represents a progress value printed by one of the threads. The lines are given in the order they were printed in.

It is guaranteed that the input is valid and matches the problem statement.

The sum of n overall test cases doesn't exceed 1500.

For each test case, print a single line with two integers, the minimum and the maximum possible overall amount of remaining work, respectively.

3
6 3
8 12 7
5
3
7
3
4
9
3 3
1000000000 999999999 999999998
1
10
1000
5 3
9 5 8
9
3
6
5
8

6 11
2999998986 2999998997
0 0