Invite the Heroes

There are $n$ cities numbered from $1$ to $n$ in a country. Two consecutive cities are connected by a bidirectional road (City $i$ is connected with city $i+1$ for each $1 \leq i \leq n-1$). There lives exactly one hero in each city. There are $k$ types of heroes. The hero of the $i$-th city has a type $t_i$.

Each hero has a power denoted by an integer number which can increase or decrease based on their activity. Initially, the hero of the $i$-th city has power $p_i$. The heroes can move from one city to another by using the roads. When a hero moves from city $i$ to $i+1$, or from city $i$ to $i-1$, the power of the hero decreases by $1$. The powers can not be negative. When the power is $0$, the hero can still move but the power does not decrease (in this case, he is inactive). Initially, each of the $n-1$ roads contains an energy drink. While passing through a road, a hero can pick the energy drink and drink it, increasing his power by $1$. An energy drink can be used exactly once.

You want to gather $k$ heroes in one city. You have to invite exactly one hero from each of the $k$ types of heroes. You want to choose the city and heroes in such a way that after gathering in that city, the sum of powers of the heroes you invited is maximum possible.

What is the maximum power you can achieve?

Input

The first line of input contains an integer $q~ (1 \leq q \leq 1000)$ $-$ the number of test cases.

The first line of each test case contains two integers $n$ and $k$ $(1 \leq k \leq n \leq 5000)$$-$denoting the number of cities and the number of types of heroes.

The next line contains $n$ integers $t_1,~ t_2,~ t_3,~ … ~t_n ~(1 \leq t_i \leq k) ~ -$ type of each hero.

The next line contains $n$ integers $p_1,~ p_2,~ p_3,~ … ~p_n ~ (1 \leq p_i \leq 10^9) ~ -$ initial power of each hero.

It is guaranteed that there exists at least one hero of each type in the input.

The sum of $n$ over all the test cases does not exceed $5000$.

Output

For each test case, print one integer $-$ the maximum possible power of the gathered heroes.

Sample

Input	Output
2 5 3 1 3 1 2 3 4 1 1 3 2 5 4 3 2 2 1 4 3 1 2 6 6	9 16
In the first test case, you can invite the heroes of the $1$st, $4$th and $5$th cities at city $4$. The power of the $1$st hero will decrease by $3$. But he can drink $3$ energy drinks kept on the streets between the city $1-2$, $2-3$ and $3-4$. The hero of the $4$th city will not lose any power. The power of the hero of the $5$th city will decrease $1$ but it will be restored after drinking the energy drink on the road between city $4$ and $5$. The total power is $4+3+2=9$. In the second test case, you can invite the heroes of the $1$st, $3$rd, $4$th and $5$th cities at city $4$. The hero of the $1$st city can drink the energy drink between the city $1-2$ and $2-3$, and leave the energy drink between the city $3-4$ for the hero of the $3$rd city. Thus he can reach city $4$ with power $2$. The hero of the $3$rd city can drink the energy drink between the city $3-4$ and reach city $4$ without losing any power. The hero of the $5$th city can drink the energy drink between the city $4-5$ and reach city $4$ with power $6$. The total power will be $2+2+6+6=16$.