Задача G. Благотворительность Марфы Геннадьевны ≡

Условие

Однажды Марфа Геннадьевна выиграла в лотерею большую сумму денег и решила потратить часть выигрыша на благотворительность.

Чтобы определить, сколько денег отдать на благотворительность, Марфа Геннадьевна придумала игру. Она записала N чисел a₁, a₂, ..., a_N по кругу (по часовой стрелке).

Начинает Марфа Геннадьевна с числа a₁. Начальная сумма денег равняется a₁. Затем Марфа Геннадьевна кидает игральный кубик (на разных гранях кубика нарисовано 1, 2, 3, 4, 5 и 6 точек). Если на кубике выпало число x, то Марфа Геннадьевна отсчитывает x чисел по часовой стрелке. Например, если выпало число 3, то Марфа Геннадьевна перейдёт от числа a₁ к числу a₄. Число, к которому перешла Марфа Геннадьевна, прибавляется к сумме. Марфа Геннадьевна бросает кубик M раз и каждый раз прибавляет очередное число к сумме.

Марфе Геннадьевне интересно, какая наибольшая сумма денег может получиться при такой игре, поэтому ей нужна программа, вычисляющая наибольшую сумму.

Формат входного файла

Входной файл содержит целые числа N M, за которыми следуют N целых чисел a₁ a₂... a_N.

Формат выходного файла

Требуется вывести в выходной файл целое число — максимальную сумму.

Ограничения

1 ≤ N ≤ 1000

0 ≤ M ≤ 5000

0 ≤ a_i ≤ 1000

Примеры тестов

7 1
1 2 3 4 5 6 7

8

7 2
1 2 3 4 5 6 7

14

5 2
5 0 10 1 6

25