Надзвичайно оригінальна задача про кістякове дерево

В Україні $n$ міст і $0$ доріг. До $30$-ої річниці незалежності пора б це виправити.

Ви хочете побудувати $n-1$ дорогу між містами таким чином, щоб ними з кожного міста можна було дістатись до будь-якого іншого. Вартість прокладання дороги між містами $i$ та $j$ рівна $(a_i+a_j)\mathrm{mod}M$ мільйонів гривень з бюджетних коштів, де $M$ — улюблене число чинного Президента України.

Яку найменшу кількість мільйонів гривень з бюджетних коштів потрібно витратити для виконання цього плану?

Giriş verilənləri

Перший рядок містить два цілих числа $n$, $M$ ($1\le n\le 200000,1\le M\le 10^9$) — число міст та улюблене число чинного Президента України відповідно.

Другий рядок містить $n$ цілих чисел $a_1,a_2,\dots ,a_n$ ($0\le a_i<M$).

Çıxış verilənləri

Виведіть найменшу кількість мільйонів гривень з бюджетних коштів, які потрібно витратити, щоб побудувати $n-1$ дорогу, щоб ними з кожного міста можна було дістатись до будь-якого іншого.

Nümunələr

Qeyd

В першому прикладі ми можемо прокласти $3$ дороги з наступними вартостями:

• Між містами $1$, $2$: $(42+69)\mathrm{mod}350=111$

• Між містами $1$, $3$: $(42+300)\mathrm{mod}350=342$

• Між містами $2$, $3$: $(69+300)\mathrm{mod}350=19$

Найвигідніше обрати дороги $(1,2)$ та $(2,3)$, з сумарною вартістю $111+19=130$.