### 问题描述 KiKi 是一个杰出的魔法师，用魔法洞察到在某片海域上有 $n$ 座藏有远古宝藏的岛屿。这些岛屿排成一条直线，依次从左往右编号，第一座岛屿编号为 $1$，第二座岛屿的编号为 $2$，一直到 $n$。每座岛屿都有一个宝藏价值，假设第 $i$ 座岛屿上的宝藏价值为 $V\left[i\right]$。 KiKi 有一个魔法棒可以使岛屿的宝藏价值成倍增加，但是增加的量和魔法棒的使用次数有关。例如,有两座岛屿宝藏价值分别为 $2,3$，一开始魔法棒没有用，假设 KiKi 使用魔法棒对岛屿 $1$ 施魔法，可以使岛屿 $1$ 的宝藏价值变为 $2\times 1$，然后 KiKi 将岛屿 $1$ 的宝藏挖出，获得 $2\times 1$ 的宝藏价值,第一座岛屿消失，然后 KiKi 再使用魔法棒对岛屿 $2$ 施魔法，可以使岛屿 $2$ 的宝藏价值变为 $3\times2$，然后将岛屿 $2$ 的宝藏挖出，可以获得 $3\times2$ 的宝藏价值。总共获得的宝藏价值为 $8$。 KiKi 有一艘海盗船可以去挖这些宝藏，所以他要挖宝藏 $n$ 次，使用的魔法棒最多次数为 $m(m\le n)$，对于每一个岛屿最多只能施法一次，而且被施法的岛屿，必须是当前要挖的那个岛屿。这些岛屿都被远古的魔法师施了魔法，每次挖宝藏只能从最左边的岛屿挖，或是从最右边的岛屿挖。每次挖宝藏之前，可以使用魔法棒使要挖的那座岛屿宝藏价值增加，即变成 $V\times time$（$V$ 表示挖的那座岛屿原来的价值，$time$ 表示魔法棒使用的次数），也可以不使用魔法棒，然后挖走宝藏，宝藏被挖走之后，这个岛屿便会消失不见了。KiKi 觉得这个问题很复杂，他不愿去想，所以让聪明的你去帮他解决这个问题，使得最后 KiKi 挖出的价值最大。 注意：在第一次挖宝藏前，魔法棒的使用次数为 $0$。 ### 输入格式 先输入一个 $T$，代表测试的数据的组数。 对于每组数据，先输入 $n,m$，接下来后面输入 $n$ 个整数（代表每座岛屿宝藏的价值）。 （$m\le n\le 100$，每座岛屿的价值不会超过 $10^{4}$）。 ### 输出描述 对于每组测试数据，输出 KiKi 能挖出最大的价值量。 ### 样例输入 ```text 2 2 2 2 3 3 3 1 3 2 ``` ### 样例输出 ```text 8 14 ```