6734: 最优 K 子段

Problem Description 给定一个序列 a1,a2,…,an，从中找出恰好 k 个不相交的连续子段，满足每一段的长度都是质数。假设其中第 i 个子段的子段和是 si，你需要最大化 min(s1,s2,…,sk)。

Input 第一行包含一个正整数 T (1≤T≤100)，表示测试数据的组数。 每组数据第一行包含两个正整数 n,k (2≤n≤200,000,1≤k≤n)。 第二行包含n 个整数 a1,a2,…,an (∣ai∣≤1000)。 输入数据保证∑n≤106，且每个ai 都是在[−1000,1000] 均匀随机生成得到（样例除外）。

Output 对于每组数据输出一行：若存在合法方案，输出一个整数，即 min(s1,s2,…,sk) 的最大可能值；若无解，输出 'impossible''。