SP5016 GUERNICA - Guernica

《格尔尼卡》是毕加索的一幅著名画作，生动再现了西班牙内战期间格尔尼卡小镇遭到轰炸的惨烈情景，反映了战争给个体尤其是无辜平民带来的悲剧。这幅画作不仅成为战后悲剧的永恒提醒，也是反战与和平的象征。 你了解到这幅画在 1992 年从普拉多博物馆搬到了索菲亚王后博物馆，于是前去参观。不过到那里时，你看到十分骇人的一幕：恶意破坏者将这幅画切割成了多块四处散落在博物馆中的碎片。一个团队已经搜集了所有能找到的 $N$ 块碎片。所有这些碎片尺寸相同！通过观察，他们发现碎片数量远远多于重建一幅《格尔尼卡》所需的数量，也就是说，这些破坏者不但拆解了原画，还拆解了几幅复制品！重建一幅《格尔尼卡》需要准确的 $P$ 块碎片。 专家们现在需要评估，每一组 $P$ 块碎片是否可能属于同一幅原画，并给每种可能的组合一个匹配分数。通过最大化总匹配分数，他们可以判断哪些碎片属于同一幅原作。你能帮他们算出所有画作的最大匹配分数吗？ 

输入包含多个测试用例。每个测试用例的第一行有两个整数 $T$ 和 $N$，分别表示测试用例的数量和碎片总数。接下来的 $N$ 行每行有一个整数 $s_i$，代表第 $i$ 块碎片的匹配分数。最后一行给出一个整数 $P$，表示重建一幅画所需的碎片数量。

对于每个测试用例，输出一行，包含测试用例编号和最大匹配分数。如果无法将所有碎片分成完整的画作组，则输出 -1。

- $1 \le T \le 10$ - $1 \le N \le 1000$ - $1 \le P \le N$ - $0 \le s_i \le 1000$ **本翻译由 AI 自动生成**