题目描述

一天，坤坤穿着背带裤和朋友们出来打球。休息时，他们 $n$ 个人坐成一圈，在玩一个游戏。一开始球在坤坤（1号）手上，每一回合，拿着球的人都可以把球传给左边或者右边的人。

已知每个人都有一个正整数得分 $a_i$。如果某次传球后，球传到了编号为 $i$ 的人手中，那么本次传球获得的得分就是 $a_{i}$。

现在坤坤想知道，球传了 $k$ 回合之后，刚好回到了自己手上时最大得分之和是多少？

注意：第 $k$ 次传球后如果球回到了 $1$ 号手中，那么这一次仍然要计入 $a_1$ 的得分。

输入格式

第一行输入两个整数 $n, k$。

第二行输入 $n$ 个正整数 $a_1, a_2, \dots, a_n$。

数据范围：

$$2\le n\le 1000, \qquad 1\le k\le 1000, \qquad 1\le a_i\le 10^9$$

输出格式

输出一个整数，表示答案。

如果不存在满足条件的传球序列，输出 -1。

5 6
5 9 1 7 4

42

4 3
3 1 2 8

-1

Hint

样例一解释： 一种最优传球方案为：

$$1\to 2\to 1\to 2\to 1\to 2\to 1$$

对应得到的总分为：

$$a_2+a_1+a_2+a_1+a_2+a_1=9+5+9+5+9+5=42$$

最后一次传回到 $1$ 号，仍然要计入 $a_1$。