You're participating in a contest for finding the 1031415926th 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 w1, w2, ..., wk (1 ≤ wi ≤ 109), the ith integer represents the amount of work assigned to the ith 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.
## Input
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 w1, w2, ..., wk (1 ≤ wi ≤ 109), the ith integer represents the amount of work assigned to the ith 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.
## Output
For each test case, print a single line with two integers, the minimum and the maximum possible overall amount of remaining work, respectively.
[samples]
**Definitions**
Let $ T \in \mathbb{Z} $ be the number of test cases.
For each test case:
- Let $ n, k \in \mathbb{Z} $, with $ 1 \leq n \leq 100 $, $ 2 \leq k \leq 16 $.
- Let $ W = (w_1, w_2, \dots, w_k) \in \mathbb{Z}^k $, where $ w_i \geq 1 $ is the work assigned to thread $ i $.
- Let $ P = (p_1, p_2, \dots, p_n) \in \mathbb{Z}^n $ be the sequence of reported progress values, in order of appearance, with $ 1 \leq p_j \leq \max(W) $, and all $ p_j $ distinct.
**Constraints**
1. Each progress value $ p_j $ corresponds to exactly one thread.
2. For each thread $ i $, its progress values (if any) form a non-decreasing sequence, and all values lie in $ [1, w_i] $.
3. No thread reports the same progress value twice.
4. Each reported progress value $ p_j $ is strictly greater than any prior progress value reported by the same thread.
5. The total number of reported progress values is $ n $, and $ n \leq k $.
**Objective**
Compute:
- $ \text{min\_remaining} $: the minimum possible total remaining work across all threads.
- $ \text{max\_remaining} $: the maximum possible total remaining work across all threads.
Let $ R_i = w_i - \max(\{ p_j \mid p_j \text{ assigned to thread } i \} \cup \{0\}) $ be the remaining work for thread $ i $.
Then:
$$
\text{min\_remaining} = \min_{\text{valid assignments}} \sum_{i=1}^k R_i, \quad \text{max\_remaining} = \max_{\text{valid assignments}} \sum_{i=1}^k R_i
$$
where the minimization and maximization are over all injective mappings of the $ n $ progress values to $ n $ distinct threads (with the rest having 0 progress), respecting the non-decreasing and distinct progress constraint per thread.