3-й этап Республиканской олимпиады по информатике 2022-2023, 1й тур

Задача B. Цена за мороженное

Ограничение по времени:

1 секунда

Ограничение по памяти:

256 мегабайт

Вы продаете мороженное. Себестоимость одного мороженного $k$ тенге. Это значит, что если вы продаете одно мороженное по $x$ тенге, тогда прибыль с одного мороженного будет $x - k$ тенге. Есть $n$ клиентов, для каждого клиента $i$ известно максимальная сумма денег $s_i$ тенге, которую он готов потратить на мороженное. Каждый клиент купить столько мороженного, сколько сможет купить. Выберите цену мороженного таким образом, чтобы максимизировать суммарную прибыль.

Формат входного файла

В первой строке находятся два целых числа $n,k$($1 <= n <= 2 \cdot 10^5$, $0 <= k <= 10^6$) — количество клиентов и себестоимость одного мороженного. Во второй строке находятся $n$ целых числа $s_1, s_2, \cdots, s_n$($1 <= s_i <= 10^6$).

Формат выходного файла

Выведите максимальную возможную прибыль.

Примеры:

Вход

5 2
8 9 10 15 12

Ответ

30

Вход

3 20
15 10 20

Ответ

0

Замечание

В первом примере одно мороженное выгодно продавать по $7$ тенге. Тогда четвертый клиент купить 2 мороженное, а остальные 4 по одному. Всего продадим 6 мороженных. Прибыль с одного мороженного $5$($7 - 2$) тенге, тогда суммарная прибыль $6 \cdot 5 = 30$ тенге. ( Temirlan Satylkhanov )