题解

题面描述

给定一个长度为 $n$ 的序列 $a$，要求将 $a$ 恰好划分为 $m$ 个非空的连续区间。对于每个区间求和得到一个新序列 $b$（长度恰好为 $m$），目标是最大化如下式子：

$b_1 + b_2 \times 2 + b_3 + b_4 \times 2 + \cdots$

题目内容

小苯有一个长度为$n$的序列$a$，他希望你能将$a$划分为恰好$m$个非空的连续段，并将其中每一段中的数字求和，组成一个长度恰好$m$的新序列$b$。接着，最大化以下式子:

$b_1+b_2×2+b_3+b_4×2...$

即：$b$中奇数位置的数字之和，加上偶数位置的数字之和$×2$

请你帮他算算这个最大值是多少吧。

输入描述

本题有多组测试数据。

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

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

第一行两个正整数$n,m(1≤m≤n≤3000)$，表示小苯的序列$a$的长度，以及需要恰好划分成的连续段个数。

第二行$n$个整数$a_i(-10^9≤a_i≤10^9)$,表示序列$a$。

(保证同一个测试文件的所有测试数据中，$n$的总和不超过$3000$。)

输出描述

对于每组测试数据:

输出一行一个整数，表示所求式子的最大值。

样例1

输入

2
5 4
1 3 2 4 3
5 1
1 3 2 4 -3

输出

23
7

说明

对于第一组测试数据，划分为: $[1, 1], [2, 2], [3,3], [4,5]$这四个区间最优,$b$={$1,3,2,7$}，最大和为:$1+3×2+2+7×2=23$