F. Flawed Prize Redemption
time limit per test
2 seconds
memory limit per test
512 megabytes
input
standard input
output
standard output

Jon has $$$n$$$ tasks and $$$m$$$ units of time. There are also $$$m$$$ cash prizes, where prize $$$j$$$ is worth $$$v_j$$$ dollars.

Task $$$i$$$ requires a duration of $$$a_i$$$ to complete. If Jon completes task $$$i$$$, he becomes eligible for cash prize $$$p_i$$$ where $$$$$$ p_i = \lfloor\frac{m}{a_i}\rfloor, $$$$$$ receiving $$$v_{p_i}$$$ dollars. If several completed tasks correspond to the same prize, Jon receives that prize only once.

Jon may choose any subset of tasks and complete them in any order, as long as the total time taken by the chosen tasks does not exceed $$$m$$$.

Find the maximum amount of money, in dollars, that Jon can receive today.

Input

The first line contains a single integer $$$t$$$ ($$$1\leq t \leq 300$$$), the number of test cases. For each test case,

  • The first line contains two integers $$$n$$$ and $$$m$$$ ($$$1\leq n,m\leq 10^5$$$), the number of tasks $$$n$$$ and available units of time $$$m$$$. There are also $$$m$$$ cash prizes.
  • The second line contains $$$n$$$ integers $$$a_1, a_2, \cdots , a_n$$$ ($$$1\leq a_i \leq m$$$), where the $$$i$$$-th integer is the duration of the $$$i$$$-th task.
  • The third line contains $$$m$$$ integers $$$v_1, v_2, \cdots, v_m$$$ ($$$1\leq v_j \leq 10^9$$$), where the $$$j$$$-th integer is the cash prize amount of the $$$j$$$-th cash prize, in dollars.
Additional constraints of input:
  • The sum of $$$n$$$ over all test cases will not exceed $$$10^5$$$.
  • The sum of $$$m$$$ over all test cases will not exceed $$$10^5$$$.
Output

$$$t$$$ lines. For each test case, output a single integer: the maximum amount of money, in dollars, that Jon can receive today.

Example
Input
2
6 10
1 2 3 4 6 10
1 5 20 1 30 1 1 1 1 60
7 12
2 3 4 5 6 11 12
1 8 18 35 1 40 1 1 1 1 1 1
Output
115
93
Note

There are two test cases.

  • For the first test case, $$$m = 10$$$. The list below gives task durations and corresponding prize indices:
    • $$$a_1 = 1$$$, $$$p_1 = \lfloor10/1\rfloor = 10$$$
    • $$$a_2 = 2$$$, $$$p_2 = \lfloor10/2\rfloor = 5$$$
    • $$$a_3 = 3$$$, $$$p_3 = \lfloor10/3\rfloor = 3$$$
    • $$$a_4 = 4$$$, $$$p_4 = \lfloor10/4\rfloor = 2$$$
    • $$$a_5 = 6$$$, $$$p_5 = \lfloor10/6\rfloor = 1$$$
    • $$$a_6 = 10$$$, $$$p_6 = \lfloor10/10\rfloor = 1$$$
    One optimal choice is to complete tasks $$$1$$$, $$$2$$$, $$$3$$$, $$$4$$$, and the total time is $$$1+2+3+4=10$$$. The total amount of money he receives is $$$60+30+20+5 = 115$$$ dollars.
  • In the second test case, one optimal choice is to complete tasks $$$1$$$, $$$2$$$ and $$$3$$$. The total time used is $$$2+3+4 = 9$$$. The cash prizes received are $$$40+35+18=93$$$.