Description

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

where $[]$ denotes an index.

Input Format

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.

Output Format

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

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

Hint

"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 B1.
idea & solution: tzc_wk; data & verification: 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.

Translated by ChatGPT 5