题目内容

在一个游戏中，有 $N$ 个连续关卡，每个关卡有一个得分（可能为负数）。玩家需要将这些关卡恰好划分为 $K$ 个连续的非空阶段，每个阶段的总分构成序列 $S_1, S_2, \dots, S_K$。计算总得分时，奇数编号的阶段（第 $1, 3, 5, \dots$ 个阶段）按原分数值累加，偶数编号的阶段（第 $2, 4, 6, \dots$ 个阶段）按原分数值的两倍累加。求所有划分方案中，可能获得的最大总得分。

本题包含多组测试数据，所有数据满足以下约束：

• 测试数据组数 $T$ 满足 $1 \le T \le 100$。
• 每组数据中，关卡数量 $N$ 和阶段数 $K$ 满足 $1 \le K \le N \le 3000$。
• 所有测试数据的 $N$ 之和不超过 $3000$。
• 每个关卡的得分 $a_i$ 满足 $|a_i| \le 10^9$。

输入描述