H. Astra's Vanguard
time limit per test
1 second
memory limit per test
256 megabytes
input
standard input
output
standard output
Mechas are the blades for exploring the ruins, and the pilots are their souls...

Deep within the Astra ruins, Little A has discovered the core energy sources of $$$K$$$ ancient mechas. The energy value of the $$$j$$$-th core is $$$E_j$$$. Meanwhile, there are $$$N$$$ candidate pilots in Little A's expedition team. Each pilot has the following four attributes:

  1. Name: A string consisting of uppercase and lowercase English letters.
  2. Sync Rate ($$$S$$$): Determines the priority to match with a mecha.
  3. Agility ($$$A$$$): The secondary assessment metric when sync rates are equal.
  4. Combat Power ($$$C$$$): Determines the destructive power when piloting a mecha.

Since there are only $$$K$$$ mechas, Little A must strictly select $$$K$$$ elites from the $$$N$$$ candidate pilots. The selection sorting rules are as follows:

  1. Prioritize pilots with a higher Sync Rate ($$$S$$$).
  2. If Sync Rates are equal, prioritize pilots with higher Agility ($$$A$$$).
  3. If the first two attributes are identical, prioritize pilots whose Names have a smaller lexicographical order.
(It is guaranteed that no two pilots have the exact same name).

After selecting these $$$K$$$ elites, Little A needs to pair them one-to-one with the $$$K$$$ energy cores. When a pilot with Combat Power $$$C_i$$$ is assigned an energy core with energy value $$$E_j$$$, the combat effectiveness generated is $$$C_i \times E_j$$$.

Little A can freely decide the assignment of energy cores among the $$$K$$$ selected pilots. Please calculate the maximum total combat effectiveness the entire vanguard team can generate.

Input

The first line contains a single integer $$$t$$$ ($$$1 \le t \le 10$$$) — the number of test cases.

For each test case: The first line contains two integers $$$N$$$ and $$$K$$$ ($$$1 \le K \le N \le 10^5$$$) — the number of candidate pilots and the number of mecha cores.

The next $$$N$$$ lines describe the pilots. The $$$i$$$-th line contains a string $$$Name_i$$$ ($$$1 \le |Name_i| \le 10$$$) and three integers $$$S_i, A_i, C_i$$$ ($$$1 \le S_i, A_i, C_i \le 10^5$$$). It is guaranteed that the names consist only of English letters and are pairwise distinct within the same test case.

The following line contains $$$K$$$ integers $$$E_1, E_2, \dots, E_K$$$ ($$$1 \le E_j \le 10^5$$$) — the energy values of the cores.

It is guaranteed that the sum of $$$N$$$ over all test cases does not exceed $$$2 \times 10^5$$$.

Output

For each test case, output a single integer on a new line, representing the maximum total combat effectiveness.

Example
Input
2
3 2
Alice 10 20 50
Bob 10 20 40
Charlie 15 10 30
10 20
4 3
David 100 100 10
Eve 100 100 100
Frank 100 90 500
Grace 90 200 1000
5 2 10
Output
1300
5520