410148: GYM103965 B Приятный плейлист

B. Приятный плейлистограничение по времени на тест1 секундаограничение по памяти на тест256 мегабайтвводстандартный вводвыводстандартный вывод

Для некоторых, кстати, осень — отличное время, чтобы посидеть дома и послушать любимые песни. Кому-то музыка больше подходит под настроение, чем постоянные прогулки в парке. У Даниила как раз освободилось немного свободного времени, чтобы послушать любимые песни, и сейчас он решает, в каком порядке их добавить в очередь.

Всего Даниил любит $$$n$$$ песен. При прослушивании $$$i$$$-й песни он получает удовольствие $$$a_i$$$. Однако, как известно, чем больше раз слушаешь одну и ту же песню подряд, тем меньше удовольствия получаешь. Формально, каждое следующее прослушивание $$$i$$$-й песни подряд уменьшает ее $$$a_i$$$ на $$$1$$$ (но не ниже нуля). Если же после $$$i$$$-й песни послушать другую, то $$$a_i$$$ возвращается к исходному значению.

Например, если есть две песни с $$$a_1 = a_2 = 2$$$, от прослушивания плейлиста $$$[1, 1, 1, 2, 1, 1]$$$ Даниил получит $$$2 + 1 + 0 + 2 + 2 + 1 = 8$$$ удовольствия в сумме.

Сейчас он хочет собрать плейлист из $$$k$$$ (возможно повторяющихся) песен так, чтобы суммарная приятность была максимальна.

К сожалению, Даниил очень торопится, поэтому выбрал следующий алгоритм действия: каждую следующую песню он будет выбирать так, чтобы она из всех доступных $$$n$$$ песен конкретно при следующем прослушивании принесла ему как можно больше удовольствия. Если же есть несколько песен, которые в данный момент принесут ему максимально возможное удовольствие от прослушивания, он выбирает любую, не совпадающую с предыдущей. Если же такой нет, то он просто продолжает слушать предыдущую песню.

Иногда такой алгоритм дает не максимально возможную сумму, но его это вполне устраивает. Помогите ему определить, какое суммарное удовольствие он в итоге получит, если будет действовать по такому алгоритму.

Входные данные

В первой строке ввода через пробел даны два целых числа $$$n$$$ и $$$k$$$ — количество песен, которые любит Даниил, и желаемый размер плейлиста ($$$1 \leqslant n \leqslant 2 \cdot 10^5$$$; $$$1 \leqslant k \leqslant 10^9$$$).

Во второй строке через пробел перечислены $$$n$$$ целых чисел $$$a_i$$$ — изначальные значения удовольствия от прослушивания каждой песни $$$(1 \leqslant a_i \leqslant 10^9)$$$.

Выходные данные

Выведите единственное целое число — удовольствие, которое можно получить от плейлиста из $$$k$$$ песен, который выбирается по описанному алгоритму.

ПримерыВходные данные

4 4
1 2 3 4

Выходные данные

14

Входные данные

5 23
1 10 7 2 3

Выходные данные

197