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 nn cities numbered from 11 to nn in a country. Two consecutive cities are connected by a bidirectional road (City ii is connected with city i+1i+1 for each 1in11 \leq i \leq n-1). There lives exactly one hero in each city. There are kk types of heroes. The hero of the ii-th city has a type tit_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 ii-th city has power pip_i. The heroes can move from one city to another by using the roads. When a hero moves from city ii to i+1i+1, or from city ii to i1i-1, the power of the hero decreases by 11. The powers can not be negative. When the power is 00, the hero can still move but the power does not decrease (in this case, he is inactive). Initially, each of the n1n-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 11. An energy drink can be used exactly once.

You want to gather kk heroes in one city. You have to invite exactly one hero from each of the kk 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 (1q1000)q~ (1 \leq q \leq 1000) - the number of test cases.

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

The next line contains nn integers t1, t2, t3,  tn (1tik) t_1,~ t_2,~ t_3,~ … ~t_n ~(1 \leq t_i \leq k) ~ - type of each hero.

The next line contains nn integers p1, p2, p3,  pn (1pi109) 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 nn over all the test cases does not exceed 50005000.

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 11st, 44th and 55th cities at city 44. The power of the 11st hero will decrease by 33. But he can drink 33 energy drinks kept on the streets between the city 121-2, 232-3 and 343-4. The hero of the 44th city will not lose any power. The power of the hero of the 55th city will decrease 11 but it will be restored after drinking the energy drink on the road between city 44 and 55. The total power is 4+3+2=94+3+2=9.

In the second test case, you can invite the heroes of the 11st, 33rd, 44th and 55th cities at city 44. The hero of the 11st city can drink the energy drink between the city 121-2 and 232-3, and leave the energy drink between the city 343-4 for the hero of the 33rd city. Thus he can reach city 44 with power 22. The hero of the 33rd city can drink the energy drink between the city 343-4 and reach city 44 without losing any power. The hero of the 55th city can drink the energy drink between the city 454-5 and reach city 44 with power 66. The total power will be 2+2+6+6=162+2+6+6=16.


Discussion

Statistics


0% Solution Ratio

Submit

Login to submit

Editorial

Here, we have to do three things optimally. Choose the targeted city, where we want to invite the ...

Toph uses cookies. By continuing you agree to our Cookie Policy.