描述

新年到了，周幽王给诸位大臣们发“年终奖”（就是国库里的锦缎）。有\(n\)匹布，每个大臣的体力都不同，可以搬\(S \sim T\)之间的锦缎数。例如\(S=2,T=4\)，就是这位大臣可以搬\(2\)匹锦缎，\(3\)匹锦缎或\(4\)匹锦缎。但每匹锦缎的价值的银子不同，当然，第一匹布和最后一匹布可以直接拿走。请问，这个大臣怎样拿才能获得价值最多的布呢。

格式

输入格式

第一行为大臣数\(t(t≤20)\)；每组数据中，第一行是锦缎个数\(n(n<1000)\)，（每位大臣挑完后会更新锦缎）第二行是\(S\)和\(T\)，第三行是每个格子上的锦缎价值\(x(x≤10^6)\)，保证最后的总价值\(≤10^{11} \)。

输出格式

输出最多可以获得的锦缎的总价值。

样例1

样例输入1

1
10
2 3
6 5 8 2 8 3 6 7 2 12

样例输出1

41

样例解释

选\(1,3,5,8,10\)这几匹锦缎可以获得\(6+8+8+7+12=41\)两银子。

来源

地址：\(vijos\)，芜湖\(OI\)团队
作者：黑暗路西法\(08\)
模拟赛\(T4\)