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

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

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

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

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

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

Формат входных данных

В первой строке ввода через пробел даны два целых числа n и k — количество песен, которые любит Даниил, и желаемый размер плейлиста (1 ≤ n ≤ 2·10⁵; 1 ≤ k ≤ 10⁹).

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

Формат выходных данных

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

Пример