Ежедневные награды Миша установил на свой телефон новую игру «Мемтест 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 4 2 1 Вывод 8 Ввод 3 3 1 2 4 Вывод 7