Problem 1094. -- 卡牌游戏III

1094: 卡牌游戏III

Time Limit: 2 Sec  Memory Limit: 128 MB
Submit: 143  Solved: 29
[Submit][Status][Web Board]

Description

菜哭武最近得到了一套卡牌,每天都喜欢拉着自己的同事们做一些游戏。这次,他拿出了N张,上面印着正整数的卡牌,排成一列,上面的数字依次是a1,a2,a3……an

他说如果有人能够在这一列卡牌中拿出三张牌,以抽走的卡牌作为分界点,将剩下的牌被分成了四部分,并且这四部分的数字和相等,那他就请这个人吃一顿饭,如果有多种情况都可以使得四部分和相等,那么他只会请找出和最大的那个人。

那么问题来了,菜哭武想知道对于某一列卡牌能够按照上面说法去掉三张,得到的每部分的和的最大值,请聪明的你帮帮他啊。

Input

题目包含多组数据。

输入的第一行有一个整数T (1T10) 代表有T组数据。

对于每组数据分为两行:

第一行有一个整数NK (其中 7≤N≤100000)

第二行有N个整数,分别是a1,a2,a3……an(1≤ai108)

Output

对于每组数据,输出的第一行为Case #x: ,其中x是数据编号(从1开始),

第二行一个整数,题中描述的K值,如果不存在输出 -1

Sample Input

2
7 
1 3 1 5 1 6 1
10
1 2 1 1 4 1 1 3 1 4

Sample Output

Case #1:
1
Case #2:
4

HINT

Source

[Submit][Status]