Купон «округлить вниз»

В школьном магазине ценники странные: все любят, когда цена делится на число a.

У Миши есть ровно один купон. Купон можно применить к одному товару (или не применять вовсе). Если купон применён к товару с ценой p, то на кассе за него возьмут самую большую цену, не превосходящую p и кратную a. То есть заплатят p - (p mod a).

Помоги Мише заплатить как можно меньше.

Формат ввода

В первой строке записаны два целых числа n и a — количество товаров в корзине и «любимое число» магазина. Во второй строке записаны n целых чисел p1, p2, ..., pn — цены товаров.

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

Выведите одно целое число — минимальную сумму, которую Миша может заплатить.

Ограничения

• 1 ≤ n ≤ 35000
• 1 ≤ a ≤ 1 000 000
• 1 ≤ pi ≤ 1 000 000

Пример

Ввод:

5 10
23 30 19 7 41

Вывод:

111

Ключевое наблюдение: купон не «пересчитывает» цену как-то сложно, он просто отбрасывает остаток при делении на a. То есть для товара с ценой p новая цена равна p - (p % a), а значит скидка на этом товаре ровно p % a.

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

План решения:

• Посчитай total = sum(p[i]) — сумму без купона.
• Для каждого товара вычисли остаток r = p[i] % a.
• Найди best = max(r) (если купон не применять, это эквивалентно скидке 0, но max и так не меньше 0).
• Ответ: total - best.

Сложность: O(n) по времени и O(1) по памяти (кроме хранения цен, если читаешь их списком).

Частая ошибка: пытаться выбирать товар с максимальной ценой. Это неверно: важен не p, а остаток p % a (например, 100 и 101 при a=10 дают скидки 0 и 1).