Надзвичайно оригінальна задача про кістякове дерево#10772
В Україні міст і доріг. До -ої річниці незалежності пора б це виправити.
Ви хочете побудувати n-1 дорогу між містами таким чином, щоб ними з кожного міста можна було дістатись до будь-якого іншого. Вартість прокладання дороги між містами та рівна (a_i + a_j)\bmod M мільйонів гривень з бюджетних коштів, де — улюблене число чинного Президента України.
Яку найменшу кількість мільйонів гривень з бюджетних коштів потрібно витратити для виконання цього плану?
Перший рядок містить два цілих числа , (1 \le n \le 200000, 1 \le M \le 10^9) — число міст та улюблене число чинного Президента України відповідно.
Другий рядок містить цілих чисел a_1, a_2, \ldots, a_n (0 \le a_i < M).
Виведіть найменшу кількість мільйонів гривень з бюджетних коштів, які потрібно витратити, щоб побудувати n-1 дорогу, щоб ними з кожного міста можна було дістатись до будь-якого іншого.
Приклад 1
Приклад 2
Приклад 3
Приклад 4
В першому прикладі ми можемо прокласти дороги з наступними вартостями:
Між містами , : (42 + 69)\bmod 350 = 111
Між містами , : (42 + 300)\bmod 350 = 342
Між містами , : (69 + 300)\bmod 350 = 19
Найвигідніше обрати дороги та , з сумарною вартістю 111+19 = 130.