Problem 1045. -- 生日礼物

1045: 生日礼物

Time Limit: 1 Sec  Memory Limit: 64 MB
Submit: 0  Solved: 0
[Submit][Status][Web Board]

Description

咕噜姐少男暗恋的女生最近要过生日了,眼看现在都大三了,为了不给自己留下遗憾,咕噜姐少男这次打算重拳出击,送一份相当有规模的生日礼物给她。经过反复思索之后,他决定给这个女孩送K束鲜花。
这天他来到了本市最大的鲜花店,发现这里所有的N束鲜花一束接着一束连成一个圆圈供顾客挑选,店主介绍说,这些鲜花是按照香味的类型排列的,也就是说,在圆圈上挨在一起的鲜花它们的香味类型是差不多的,尽管咕噜姐少男打算买很多花,但由于他很追求完美,所以他希望他买的花香味不要过于接近,因此他决定不买挨在一起的花。举个简单的例子,假如这个店一共有A、B、C、D、E、F这6束花,并且按照下图方式排列成圆圈,那么如果他买了A,他就绝不会再买F和B中的任何一束:

另外,由于每束花除了有一个香味的种类之外,也有一个芳香程度,因此咕噜姐少男自然希望他买的K束花芳香程度之和最大。
不过由于这个店的鲜花数量实在非常惊人,而他又迫切想做得尽量完美不出差错,因此他希望你写一个程序告诉他应该选哪K束花。

Input

输入数据第一行为一个整数T,表示接下来一共有T组测试数据。每组测试数据的格式如下:

第一行为两个整数N,K(1≤N,K≤10000)。
从第2行到第K+1行每行一个整数,第i个整数Vi表示按顺时针方向第i束花的芳香程度(-10000≤Vi≤10000)。

Output

输出共T行,每行要么为一个整数,要么为一个字符串“Impossible”。假如第i组数据中不存在买K束花的方案,请在第i行输出“Impossible”(输出不含引号),否则请在第i行输出整数Ai,表示选出的K束花的芳香程度之和。

Sample Input

4
3 1
1
2
3
7 3
1
2
1
1
2
1
1
6 3
2
1
1
3
1
2
2 2
1
2

Sample Output

3
5
6
Impossible

HINT

Source

[Submit][Status]