#####   ######  #####    ###    #   #  ###  #   #  ######
##  ##  ##      ##  ##  ## ##   #   #   #   #   #  ##
#####   ####    #####   #   #   #   #   #   #   #  ####
##  #   ##      ##      ## ##    # #    #    # #   ##
##   #  ######  ##       ###      #    ###    #    ######

$ curl repovive.com/contests/8/problems/e

░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░█████████████████████████████████████████

#####   ######  #####    ###    #   #  ###  #   #  ######
##  ##  ##      ##  ##  ## ##   #   #   #   #   #  ##
#####   ####    #####   #   #   #   #   #   #   #  ####
##  #   ##      ##      ## ##    # #    #    # #   ##
##   #  ######  ##       ###      #    ###    #    ######

$ curl repovive.com/contests/8/problems/e

Repovive

One Difference Swap - Repovive Standard Round 3 | Repovive | Repovive

Back

Code

Upload

Submissions

Learn

8E. One Difference Swap

2500 ptstype :zen to enter zen mode

by mohammadsam ansaripoor

Time: 2sMemory: 256 MB

You are given an array $a_1, a_2, \ldots, a_n$ of positive integers.

In one operation, you may choose an adjacent pair $(a_i, a_{i+1})$ such that $|a_i - a_{i+1}| = 1$ , and swap their positions. You may perform this operation any number of times.

Let $\mathcal{R}$ be the set of all arrays reachable from $a$ through these operations. Your goal is to maximize the sum of the first $k$ elements:

$\max_{b \in \mathcal{R}} \; \sum_{i=1}^{k} b_i$

Find this maximum value.

Constraints

$1 \le t \le 10^4$
$1 \le k \le n$
$1 \le n \le 2 \times 10^5$
$1 \le a_i \le 10^6$
The sum of $n$ over all test cases is at most $2 \times 10^5$

Input

t

\left. \begin{array}{l} n \quad k \\ a_1 \quad a_2 \quad \cdots \quad a_n \end{array} \right\} \times t

Output

\left. \begin{array}{l} ans \end{array} \right\} \times t

Samples

Input

Case 1

3 2
1 2 100

Case 2

3 2
1 2 3

Case 3

5 2
2 2 3 7 5

Case 4

5 4
7 6 4 7 8

Case 5

6 4
8 7 6 1 2 3

Explanation

Case 1

The only eligible swap is between the first two elements (since $|1-2|=1$ ), but swapping them leaves the sum unchanged at $1+2=3$ . The third element $100$ cannot be swapped with $2$ because $|2-100| \neq 1$ , so $3$ is optimal.

Case 2

Start with $[1,2,3]$ and swap $a_2$ with $a_3$ (since $|2-3|=1$ ) to obtain $[1,3,2]$ , giving a sum of $1+3=4$ .

Case 3

Initially the sum is $2+2=4$ . Swapping $a_2$ with $a_3$ (since $|2-3|=1$ ) yields $[2,3,2,7,5]$ , giving a sum of $2+3=5$ .

Case 4

Initially the sum of the first four elements is $7+6+4+7=24$ . Swap $a_4$ with $a_5$ (since $|7-8|=1$ ) to obtain $[7,6,4,8,7]$ , giving a sum of $7+6+4+8=25$ .

Case 5

Initially the sum of the first four elements is $8+7+6+1=22$ . Swap $a_4$ with $a_5$ (since $|1-2|=1$ ) to obtain $[8,7,6,2,1,3]$ , giving a sum of $8+7+6+2=23$ .

Output

Case 1

Case 2

Case 3

Case 4

Case 5

You are given an array $a_1, a_2, \ldots, a_n$ of positive integers.

In one operation, you may choose an adjacent pair $(a_i, a_{i+1})$ such that $|a_i - a_{i+1}| = 1$ , and swap their positions. You may perform this operation any number of times.

Let $\mathcal{R}$ be the set of all arrays reachable from $a$ through these operations. Your goal is to maximize the sum of the first $k$ elements:

$\max_{b \in \mathcal{R}} \; \sum_{i=1}^{k} b_i$

Find this maximum value.

$1 \le t \le 10^4$
$1 \le k \le n$
$1 \le n \le 2 \times 10^5$
$1 \le a_i \le 10^6$
The sum of $n$ over all test cases is at most $2 \times 10^5$

t

\left. \begin{array}{l} n \quad k \\ a_1 \quad a_2 \quad \cdots \quad a_n \end{array} \right\} \times t

\left. \begin{array}{l} ans \end{array} \right\} \times t

Start with $[1,2,3]$ and swap $a_2$ with $a_3$ (since $|2-3|=1$ ) to obtain $[1,3,2]$ , giving a sum of $1+3=4$ .

Initially the sum is $2+2=4$ . Swapping $a_2$ with $a_3$ (since $|2-3|=1$ ) yields $[2,3,2,7,5]$ , giving a sum of $2+3=5$ .

Initially the sum of the first four elements is $7+6+4+7=24$ . Swap $a_4$ with $a_5$ (since $|7-8|=1$ ) to obtain $[7,6,4,8,7]$ , giving a sum of $7+6+4+8=25$ .

Initially the sum of the first four elements is $8+7+6+1=22$ . Swap $a_4$ with $a_5$ (since $|1-2|=1$ ) to obtain $[8,7,6,2,1,3]$ , giving a sum of $8+7+6+2=23$ .