最优 K 子段

Problem Description

给定一个序列 $a_1,a_2,\dots,a_n$，从中找出恰好 $k$ 个不相交的连续子段，满足每一段的长度都是质数。假设其中第 $i$ 个子段的子段和是 $s_i$，你需要最大化 $\min(s_1,s_2,\dots,s_k)$。

Input

第一行包含一个正整数 $T$ ($1\leq T\leq 100$)，表示测试数据的组数。 每组数据第一行包含两个正整数 $n,k$ ($2\leq n\leq 200\,000$, $1\leq k\leq n$)。 第二行包含 $n$ 个整数 $a_1,a_2,\dots,a_n$ ($|a_i|\leq 1000$)。 输入数据保证 $\sum n\leq 10^6$，且每个 $a_i$ 都是在 $[-1000,1000]$ 均匀随机生成得到（样例除外）。

Output

对于每组数据输出一行：若存在合法方案，输出一个整数，即 $\min(s_1,s_2,\dots,s_k)$ 的最大可能值；若无解，输出 ''$\texttt{impossible}$''。

Sample Input

4
6 1
1 1 4 5 1 4
6 1
-1 -1 -4 -5 -1 -4
6 3
-1 -1 -4 -5 -1 -4
2 2
0 0

Sample Output

15
-2
-9
impossible

Source

2024“钉耙编程”中国大学生算法设计超级联赛（4）