题解

题面描述

给定一个长度为 $n$ 的序列 $a$。你需要将该序列划分为 $m$ 个不相交的连续区间，记为 $[l_1,r_1],[l_2,r_2],\ldots,[l_m,r_m]$，其中必须满足对于任意 $j$ 满足 $r_j+1=l_{j+1}$。定义区间函数为
$f(l_j, r_j)$= max($a_{l_j}$,$a_{l_j+1}$,......,$a_{r_j}$) 得到的新序列为
$b = \{f(l_1, r_1),f(l_2, r_2),\ldots,f(l_m, r_m)\}$ 要求使得 $b_1+b_2+\ldots+b_m$ 最大化，求该最大值。

题目内容

小苯有一个长度为$n$的序列。他将$a$分为了$m$个不相交的连续段，每个段内的最大值构成了一个新的序列$b$。

现在小笨给定了你$n$序列，他希望最大化序列$b$的总和,请你帮他算一算$b$数组的总和最大可以达到多少吧

更正式的，小苯限定你可以将序列n划分为了$m$个区间

$[l_1,r_1],[l_2,r_2],...,[l_m,r_m]$,需要满足:

• 对于任意$j(1≤j<m)$均有:$r_j+1=l_{j+1}$

定义$f(l_j,r_j)=max({a_l}_j,{a_l}_{j+1},...{a_r}_j)$则

$b=${$f(l_1,r_1),f(l_2,r_2),..,f(l_m,r_m)$}

给定$n,m,a$,求$b_1+b_2+...+b_m$的最大值。

输入描述

本题有多组测试数据。

输入的第一行包含一个正整数$T(1≤T≤100)$,表示数据组数。

接下来包含$T$组数据，每组数据的格式如下:

第一行两个正整数$n,m(1≤m≤n≤2×10^5)$分别表示序列a的长度和需要划分的区间段数。

第二行$n$个正整数$a(1≤a≤10^9)$表示序列$a$ (保证同一个测试文件中的所有测试数据里，$n$的总和不超过$2×10^5$。)

输出描述

对于每组测试数据:

在单独的一行输出一个整数，表示最优划分下，$b$的最大总和。

样例1

输入

2
5 2
1 6 2 5 4
4 2
1 1 1 1

输出

11
2