Ежедневные награды
Миша установил на свой телефон новую игру «Мемтест 2к17». В ней предусмотрены ежедневные награды за посещение. Награды бывают n уровней. Тип награды зависит от награды за предыдущий день, а именно:
если игрок в предыдущий день не посещал игру, то за сегодняшнее посещение он получит награду уровня 1;
если игрок в предыдущий день зашёл в игру и получил награду уровня k
(k≠n), то за сегодняшнее посещение он получит награду уровня k+ 1;
если игрок в предыдущий день зашёл в игру и получил награду уровня n
, то за сегодняшнее посещение он получит награду уровня 1.
На Форуме для Крутых Программистов Миша выяснил, что награды каждого из уровней составляют соответственно a1,a2, ...,an
золотых монет. Через m дней состоится турнир по «Мемтест 2к17», к которому Миша хочет собрать как можно больше золотых монет. Помогите ему спланировать посещения игры на протяжении m дней, оставшихся до турнира. Найдите наибольшее количество золотых монет, которое он сможет получить за счёт ежедневных наград в этот период. Можно считать, что игра установлена в первый из этих m дней, то есть до этого Миша в неё ни разу не заходил.
Входные данные
Первая строка входных данных содержит натуральные числа n
и m (1 ≤n,m≤ 1000) — количества уровней наград и дней до турнира.
Вторая строка входных данных содержит n
целых чисел a1,a2, ...,an (1 ≤ai≤ 1000), где ai — величина награды i−го уровня в золотых монетах.
Выходные данные
Выведите одно натуральное число — наибольшее количество золотых монет, которое Миша сможет получить до турнира.
Примечание
В первом тесте из примера Мише выгодно заходить в игру каждый день. Тогда он получит 1 + 2 + 4 = 7 золотых монет.
Во втором тесте из примера Мише выгодно заходить в игру в первый и третий день, получив в каждый из них по 4
монеты, тогда в сумме он получит 8 монет.
Примеры
Ввод Вывод
3 3 7
1 2 4
3 3 8
4 2 1
Вот мои наработки, но не получается. выводит неверный ответ:
n, m = map(int, input().split())
a = list(map(int, input().split()))
res = 0
i = 0
b = 1
while i < m:
if b == n + 1:
b = 0
res += a[0]
else:
if i <= m - 3:
if a[0] * 2 > a[b - 1] + a[b] + a[b + 1]:
res += a[0] * 2
b = 0
i += 2
else:
res += a[b - 1]
else:
res += a[b - 1]
b += 1
i += 1
print(res)
