B. Цена за мороженое
Ограничение по времени на тест: 1 секунда
Ограничение по памяти на тест: 256 мегабайт
Ввод: стандартный ввод
Вывод: стандартный вывод
Вы продаёте мороженое. Себестоимость одного мороженого k тенге. Это значит, что если вы продаёте одно мороженое по x тенге, то прибыль с одного мороженого будет x − k тенге.

Есть n клиентов, для каждого клиента i известна максимальная сумма денег sᵢ тенге, которую он готов потратить на мороженое. Каждый клиент купит столько мороженого, сколько сможет купить. Выберите цену мороженого таким образом, чтобы максимизировать суммарную прибыль.

Входные данные
В первой строке находятся два целых числа n, k (1 ≤ n ≤ 2⋅10⁵, 0 ≤ k ≤ 10⁶) — количество клиентов и себестоимость одного мороженого.

Во второй строке находятся n целых чисел s₁, s₂, ..., sₙ (1 ≤ sᵢ ≤ 10⁶).

Выходные данные
Выведите максимальную возможную прибыль.
В первом примере одно мороженое выгодно продавать по 7 тенге. Тогда четвёртый клиент купит 2 мороженых, а остальные 4 по одному. Всего продадим 6 мороженых. Прибыль с одного мороженого 5 (7 − 2) тенге, тогда суммарная прибыль 6 ⋅ 5 = 30 тенге.

0 0 Пожаловаться