A. Strange Birthday Party
binary search; dp; greedy; sortings; two pointers
Petya organized a strange birthday party. He invited \(n\) friends and assigned an integer \(k_i\) to the \(i\)-th of them. Now Petya would like to give a present to each of them. In the nearby shop there are \(m\) unique presents available, the \(j\)-th present costs \(c_j\) dollars (\(1 \le c_1 \le c_2 \le \ldots \le c_m\)). It's not allowed to buy a single present more than once.For the \(i\)-th friend Petya can either buy them a present \(j \le k_i\), which costs \(c_j\) dollars, or just give them \(c_{k_i}\) dollars directly.Help Petya determine the minimum total cost of hosting his party.
The first input line contains a single integer \(t\) (\(1 \leq t \leq 10^3\)) — the number of test cases.The first line of each test case contains two integers \(n\) and \(m\) (\(1 \leq n, m \leq 3 \cdot 10^5\)) — the number of friends, and the number of unique presents available.The following line contains \(n\) integers \(k_1, k_2, \ldots, k_n\) (\(1 \leq k_i \leq m\)), assigned by Petya to his friends. The next line contains \(m\) integers \(c_1, c_2, \ldots, c_m\) (\(1 \le c_1 \le c_2 \le \ldots \le c_m \le 10^9\)) — the prices of the presents.It is guaranteed that sum of values \(n\) over all test cases does not exceed \(3 \cdot 10^5\), and the sum of values \(m\) over all test cases does not exceed \(3 \cdot 10^5\).
For each test case output a single integer — the minimum cost of the party.
In the first example, there are two test cases. In the first one, Petya has \(5\) friends and \(4\) available presents. Petya can spend only \(30\) dollars if he gives \(5\) dollars to the first friend. A present that costs \(12\) dollars to the second friend. A present that costs \(5\) dollars to the third friend. A present that costs \(3\) dollars to the fourth friend. \(5\) dollars to the fifth friend. In the second one, Petya has \(5\) and \(5\) available presents. Petya can spend only \(190\) dollars if he gives A present that costs \(10\) dollars to the first friend. A present that costs \(40\) dollars to the second friend. \(90\) dollars to the third friend. \(40\) dollars to the fourth friend. \(10\) dollars to the fifth friend.