Бізнес#517

Бізнес

1 секунда
256 мегабайтів
Складна

Скоро пану Бену виповниться вісімдесят років, він залишився зовсім без занять, тож вирішив відкрити ще один бізнес. Цього разу він розмістив автоматів із газованою водою в найближчому торговому центрі та пронумерував їх від до . Кожен автомат може містити до доларів, і в деякі з них пан Бен заздалегідь поклав гроші, щоб видавати решту. Зокрема, автомат з номером (1 \leq i \leq n) спочатку містить a_i (0 \leq a_i < x) доларів.

Протягом наступних 10^{100} днів наприкінці кожного дня відбувається наступне:

  1. Кількість доларів у кожному автоматі збільшується на .

  2. Якщо після цього збільшення кількість доларів у певному автоматі стає не меншою за , помічник пана Бена забирає з нього всі гроші, і в автоматі стає доларів.

Як бухгалтер пана Бена, знайдіть максимальну сумарну кількість доларів у всіх автоматах після днів для деякого цілого (1 \leq t \leq 10^{100}).

Вхідні дані

Перший рядок містить два цілі числа (1 \leq n \leq 2 \cdot 10^5, 2 \leq x \leq 10^{12}) — кількість автоматів і максимальна кількість доларів в одному автоматі відповідно.

Другий рядок містить цілих чисел a_1, a_2, \ldots, a_n (0 \leq a_i < x) — початкову кількість доларів у кожному автоматі.

Вихідні дані

Виведіть одне ціле число — максимальну сумарну кількість грошей у всіх автоматах після деякого дня.

Приклади

Приклад 1

Loading
Loading

Приклад 2

Loading
Loading

Примітка

У першому прикладі після -го дня кількість доларів в автоматах дорівнює (), тому сумарна кількість доларів становить 1+2+2=5, і це є максимальним значенням серед усіх днів.

У другому прикладі після -го дня кількість доларів в автоматах дорівнює (2,2,2,5,5,5,6,6), тому сумарна кількість доларів становить , і це є максимальним значенням серед усіх днів. Наприклад, після інших днів кількість доларів в автоматах така:

  • Після -го дня кількість доларів дорівнює (6,6,6,2,2,2,3,3), тому сумарна кількість доларів становить .

  • Після -го дня кількість доларів дорівнює (1,1,1,4,4,4,5,5), тому сумарна кількість доларів становить .

  • Після -го дня кількість доларів дорівнює (4,4,4,0,0,0,1,1), тому сумарна кількість доларів становить .

Оцінювання

  1. ( балів) x = 2;

  2. ( балів) n \leq 1000, x \leq 1000;

  3. ( балів) n \leq 100;

  4. ( балів) x \leq 10^5;

  5. ( балів) без додаткових обмежень.