# Practice on Toph

Participate in exhilarating programming contests, solve unique algorithm and data structure challenges and be a part of an awesome community.

# Invite the Heroes

By adnan_toky · Limits 2.5s, 512 MB

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

InputOutput
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$.

### Statistics

0% Solution Ratio