题目背景

本题是 My rating is ... 的 easy 版本。注意题目限制和数据范围与 hard 版本不同。

请注意特殊的时空限制，题目描述下方有简化题意。

My rating is -32.

说明：上方的帖子是机房里某个同学很久很久以前的黑历史，现在成了机房传世经典，不是为了出比赛才发的，请不要误会。

题目描述

小 A 想在 Codeforces 上发 $n$ 篇帖子！例如：

“My rating is 1064.”

“I am PolarSea.”

“你知道 phi 吗？你知道你的 phi 处是哪里吗？你知道它的 price 吗？1e9 + 7。”

“每道题都很简单，全场虐题不用烦。T1 到场先签到，T2 上手随便切，T3 一交就能过，T4 稍想也能 A。DP 转移很容易，数学结论尽皆知。建图方法极明显，数据结构很一般。不卡空间不卡常，码量不大手不酸。没有毒瘤大模拟，只有良多大水题。片刻四题提交过，人人 AK 笑开颜。”

“……”

为此，小 A 新注册了 $k$ 个账号。他决定按照从 $1$ 到 $n$ 的顺序发出每篇帖子，并用到所有 $k$ 个账号。不过刷屏过多会引起 Mike 的注意并被封号，小 A 当然不希望这样：他进行了一些评估，得到了每篇帖子的安全指数 $a_i$，表示他发出第 $i$ 篇帖子后不被封号的概率。

由于第一印象非常重要，小 A 定义一个账号的安全指数为该账号所发出的第一篇帖子的安全指数。此外，如果用同一个账号连续发出两个帖子，Mike 会立刻封掉这个账号，因此这种情况是不合法的。

小 A 希望找到这样一个发帖方案，使得所有账号的安全指数之和最大。你只需要求出安全指数之和的最大值即可。

---

「简化题意」

将 $1\sim n$ 不重不漏地分进 $k$ 个集合 $S_1,S_2,\cdots,S_k$ 中，满足相邻的数不在同一集合 且 $|S_i|>0$。求

$$\sum_{i=1}^k a[{\min_{j\in S_i}j}]$$

的最大值，其中 $[]$ 表示下标。

输入格式

本题有多组数据。

第一行一个整数 $t$，表示该测试点编号。
第二行一个整数 $T$，表示数据组数。

对于每组数据：

第一行两个整数 $n,k$。
第二行 $n$ 个整数 $a_1,a_2,\cdots,a_n$ 表示每个帖子的安全指数。

输出格式

对于每组数据，一行一个整数表示答案。

0
3
4 2
1 1 3 2
8 3
1 3 2 8 6 4 7 5
40 10
9843011 22841896 42690334 3412396 8420789 100693326 23390709 11537210 145661796 21418321 16914724 146120903 14287416 9157773 259599687 16469809 13371424 221660485 23554750 3004543 19382066 514113557 959488450 162305801 377127750 240963428 597774302 18789772 647693870 517468301 547221960 162988230 309004668 267293109 867629494 476230153 70400563 100943563 140708197 999999999

2
12
5684074840

提示

「样例 1 说明」

小 A 只能使用账号 $1$ 发帖子 $1$ 和 $3$，剩下的帖子用账号 $2$ 发。其安全程度为 $a_{\min(1,3)}+a_{\min(2,4)}=2$。

「数据范围与约定」

本题共有 6 个测试点。

• Testcase #0（1 points）：是样例。
• Testcase #1（10 points）：$k=2$。
• Testcase #2（30 points）：$n\leq 10$，$k\leq 4$。
• Testcase #3（15 points）：$k=3$。
• Testcase #4（20 points）：$n\leq 64$，$k\leq 7$。
• Testcase #5（24 points）：无特殊限制。

对于 $100\%$ 的数据，$2 \leq k \leq n \leq 10^4$，$0 \leq a_i \leq 10^9$，$T=10$。
对于所有测试点，时间限制 200ms，空间限制 16MB。

「题目来源」

Sweet Round 07 B1。
idea & solution：tzc_wk；data & 验题：Alex_Wei。

My rating is -32. My rating is -32. My rating is -32. My rating is -32. My rating is -32. My rating is -32. My rating is -32. My rating is -32. My rating is -32. My rating is -32. My rating is -32. My rating is -32. My rating is -32. My rating is -32. My rating is -32. My rating is -32. My rating is -32. My rating is -32. My rating is -32. My rating is -32. ……

Upvote -43 Downvote                  PolarSea