P7874 "SWTR-7" My rating is -32 (easy version)

#### This problem is the easy version of My rating is .... Note that the constraints and data range are different from the [hard](https://www.luogu.com.cn/problem/P7878) version. #### Please pay attention to the special time and memory limits. A simplified statement is provided below the description. [My rating is -32.](https://codeforces.com/blog/entry/71123) Note: The post above is an ancient dark history of someone in the lab room, and it has now become a classic legend there. It was not posted to create a contest, so please do not misunderstand.

Little A wants to post $n$ posts on Codeforces. For example: > “My rating is 1064.” > > “I am PolarSea.” > > “Do you know phi? Do you know where your phi point is? Do you know its price? 1e9 + 7.” > > “Every problem is very easy, no need to worry about crushing the whole contest. Sign in as soon as you arrive for T1, casually solve T2, T3 passes right after submission, and T4 can also be accepted with a bit of thought. DP transitions are easy, math conclusions are all well-known. Graph building methods are obvious, data structures are nothing special. No memory or constant tricks, not much code and your hands will not get tired. No nasty huge simulations, only lots of very easy problems. Submit four problems in a moment, everyone gets AK and smiles.” > > “……” For this, Little A registered $k$ new accounts. He decides to post each post **in order from $1$ to $n$**, and **use all $k$ accounts**. However, posting too much will attract Mike’s attention and lead to bans, which Little A of course does not want. After some evaluation, he obtained the safety index $a_i$ for each post, meaning the probability of not being banned after posting the $i$-th post. Since first impressions are very important, Little A defines the safety index of an account as the safety index of the **first** post made by that account. Also, if **two consecutive posts are made using the same account**, Mike will immediately ban that account, so this situation **is invalid**. Little A wants to find a posting plan that maximizes the sum of safety indices of all accounts. You only need to output the maximum possible sum. --- **"Simplified Statement"** Partition $1\sim n$ **without repetition and without omission** into $k$ non-empty sets $S_1,S_2,\cdots,S_k$, satisfying that **adjacent numbers are not in the same set** and $|S_i|>0$. Maximize $$\sum_{i=1}^k a[{\min_{j\in S_i}j}]$$ where $[]$ denotes an **index**.

**This problem contains multiple test cases.** The first line contains an integer $t$, which denotes the test point ID. The second line contains an integer $T$, which denotes the number of test cases. For each test case: The first line contains two integers $n,k$. The second line contains $n$ integers $a_1,a_2,\cdots,a_n$, representing the safety index of each post.

For each test case, output one integer per line, representing the answer.

**"Sample 1 Explanation"** Little A can only use account $1$ to post posts $1$ and $3$, and use account $2$ for the remaining posts. The total safety is $a_{\min(1,3)}+a_{\min(2,4)}=2$. **"Constraints and Notes"** This problem has 6 test points in total. - Testcase #0 (1 points): the sample. - 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): no special restrictions. For $100\%$ of the data, $2 \leq k \leq n \leq 10^4$, $0 \leq a_i \leq 10^9$, $T=10$. For all test points, **time limit is 200ms, memory limit is 16MB.** **"Source"** [Sweet Round 07](https://www.luogu.com.cn/contest/) B1. idea & solution: [tzc_wk](https://www.luogu.com.cn/user/115194); data & verification: [Alex_Wei](https://www.luogu.com.cn/user/123294). > **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**. Translated by ChatGPT 5