Продажа билетов


Отправить решение Решать в редакторе

Сложность: 40%
Очки: 100 (частичный балл)
Ограничение по времени: 1.0s
Ограничение по памяти: 256M

Автор:
Тип задачи
Разрешённые языки
C, C#, C++, F#, Go, Java, JavaScript, Kotlin, Pascal, Python, Scratch

Продажа билетов

В кассе n рядов, в ряду i осталось c_i билетов. Цена билета равна числу оставшихся билетов в этом ряду на момент покупки (после продажи цена в ряду падает на 1). Касса продаёт k билетов в любом порядке. Какая наибольшая выручка возможна?

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

В первой строке числа n и k (1 ≤ n ≤ 200000, 1 ≤ k ≤ c_1 + ... + c_n). Во второй строке n чисел c_i (1 ≤ c_i ≤ 10^9). Сумма c_i не превосходит 10^12.

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

Максимальная выручка по модулю 1000000007.

Примеры

Пример 1

Ввод:

2 4
2 5

Вывод:

14
Пример 2

Ввод:

1 3
4

Вывод:

9

Комментарии

Еще нет ни одного комментария.