Скоро пану Бену виповниться вісімдесят років, він залишився зовсім без занять, тож вирішив відкрити ще один бізнес. Цього разу він розмістив автоматів із газованою водою в найближчому торговому центрі та пронумерував їх від до . Кожен автомат може містити до доларів, і в деякі з них пан Бен заздалегідь поклав гроші, щоб видавати решту. Зокрема, автомат з номером (1 \leq i \leq n) спочатку містить a_i (0 \leq a_i < x) доларів.
Протягом наступних 10^{100} днів наприкінці кожного дня відбувається наступне:
Кількість доларів у кожному автоматі збільшується на .
Якщо після цього збільшення кількість доларів у певному автоматі стає не меншою за , помічник пана Бена забирає з нього всі гроші, і в автоматі стає доларів.
Як бухгалтер пана Бена, знайдіть максимальну сумарну кількість доларів у всіх автоматах після днів для деякого цілого (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
Приклад 2
У першому прикладі після -го дня кількість доларів в автоматах дорівнює (), тому сумарна кількість доларів становить 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), тому сумарна кількість доларів становить .
( балів) x = 2;
( балів) n \leq 1000, x \leq 1000;
( балів) n \leq 100;
( балів) x \leq 10^5;
( балів) без додаткових обмежень.