Fight Club Restored

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 $n$ fighters numbered $1$ to $n$ . The strength of the $i$ th fighter is $S_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 $n$ days and people can bet on the fighters.
On the $i$ th day ${(1 \le i \le n)}$ , anyone can bet on the $i$ th fighter where the $i$ th fighter, on that day, will fight with ${i+1, i+2, \dots, n}$ th fighters.
If $i$ th fighter wins a battle, the bettor will win $1$ taka (the currency of the fight club) and if the fighter loses, the bettor will lose $1$ taka.

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

Now, Sifat, one of the bettors, wants to bet for maximum $k$ 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 $k$ days.

Input

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

The first line of the each test case contains two integers, $n$ ${(1 \le n \le 3\times 10^5)}$ and $k$ ${(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 $n$ space-separated integers ${S_1, S_2, \dots, S_n}$ ${(1 \le S_i \le 10^9)}$ denoting strength of each fighter.

It is guaranteed that sum of $n$ over all test cases will not exceed ${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

Input	Output
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 $1$ st day, Sifat can win $4$ taka. As, he bets on $1$ st day, he has to bet on $2$ nd day and he can’t bet on $3$ rd day. So, by betting on $2$ nd day, he can win $3$ taka. Then, by betting on $4$ th day, he can win $1$ taka, by betting on $5$ th day (he bets on $4$ th day, so he has to bet on $5$ th day), he can’t won any money as no battle can happen and as $6$ th day doesn’t exist, it doesn’t matter. So, by betting in total $4$ days (which is less than given $k$ ) Sifat can win total ${(4+3+1)=8}$ taka. It can be shown that it is the maximum amount. In the third test case, Sifat bets on maximum $2$ days. So, by betting on $2$ nd and $3$ rd day, he can win maximum $1$ taka.

Input

Output

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 $1$ st day, Sifat can win $4$ taka. As, he bets on $1$ st day, he has to bet on $2$ nd day and he can’t bet on $3$ rd day. So, by betting on $2$ nd day, he can win $3$ taka. Then, by betting on $4$ th day, he can win $1$ taka, by betting on $5$ th day (he bets on $4$ th day, so he has to bet on $5$ th day), he can’t won any money as no battle can happen and as $6$ th day doesn’t exist, it doesn’t matter. So, by betting in total $4$ days (which is less than given $k$ ) Sifat can win total ${(4+3+1)=8}$ taka. It can be shown that it is the maximum amount.

In the third test case, Sifat bets on maximum $2$ days. So, by betting on $2$ nd and $3$ rd day, he can win maximum $1$ taka.