Fight Club Restored

rifatrraazz Replay of Ada Lovelace Na...
Limits 1s, 512 MB

The things you own, end up owning you. It’s only after we’ve lost everything that we’re free to do anything.

Tyler Durden’s Fight Club has been restored by Shahriar. Let’s walk through it.

There are nn fighters numbered 11 to nn. The strength of the iith fighter is SiS_i. In a battle between two fighters, the fighter with the higher strength will win. If the strength of the two fighters is equal, the fighter with the smaller number will win.

Of course, you do not talk about fight club. Besides, there are some new rules for the fight club as follows:

  • There will be fighting battles for nn days and people can bet on the fighters.

  • On the iith day (1in){(1 \le i \le n)}, anyone can bet on the iith fighter where the iith fighter, on that day, will fight with i+1,i+2,,n{i+1, i+2, \dots, n}th fighters.

  • If iith fighter wins a battle, the bettor will win 11 taka (the currency of the fight club) and if the fighter loses, the bettor will lose 11 taka.

The bettor can not bet for a single day or consecutively 33 days. In other words, if a person bets on the iith day, then the person has to bet on the (i+1)(i+1)th day and they can not bet on the (i+2)(i+2)th day.

Now, Sifat, one of the bettors, wants to bet for maximum kk days and you want to join the fight club. Shahriar will let you join if you can find the maximum amount of money (in taka) Sifat can win by betting not more than kk days.

Input

The first line of the input contains an integer, tt (1t104){(1 \le t \le 10^4)} denoting the number of test cases.

The first line of the each test case contains two integers, nn (1n3×105){(1 \le n \le 3\times 10^5)} and kk (1kmin(200,n)){(1 \le k \le min(200, n))} denoting the number of fighters (battle days too) and number of maximum days Sifat will bet respectively.

The second line of the each test case contains nn space-separated integers S1,S2,,Sn{S_1, S_2, \dots, S_n} (1Si109){(1 \le S_i \le 10^9)} denoting strength of each fighter.

It is guaranteed that sum of nn over all test cases will not exceed 3×105{3 \times 10^5}.

Output

For each testcase, print an integer denoting the maximum amount of money (in taka) Sifat can win if he has no money initially.

Sample

InputOutput
3
1 1
12
5 5
7 5 1 3 3
4 2
10 121 1111 111
0
8
1

In the first test case, as there are only one fighter, no battle can happen, Sifat can’t win any money.

In the second test case, by betting on 11st day, Sifat can win 44 taka. As, he bets on 11st day, he has to bet on 22nd day and he can’t bet on 33rd day. So, by betting on 22nd day, he can win 33 taka. Then, by betting on 44th day, he can win 11 taka, by betting on 55th day (he bets on 44th day, so he has to bet on 55th day), he can’t won any money as no battle can happen and as 66th day doesn’t exist, it doesn’t matter. So, by betting in total 44 days (which is less than given kk) Sifat can win total (4+3+1)=8{(4+3+1)=8} taka. It can be shown that it is the maximum amount.

In the third test case, Sifat bets on maximum 22 days. So, by betting on 22nd and 33rd day, he can win maximum 11 taka.


Submit

Login to submit.

Statistics

86% Solution Ratio
BrehamPieEarliest, 7M ago
S_SubrataFastest, 0.2s
S_SubrataLightest, 9.3 MB
serotoninShortest, 958B
Toph uses cookies. By continuing you agree to our Cookie Policy.