Надзвичайно оригінальна задача про кістякове дерево
Надзвичайно оригінальна задача про кістякове дерево
В Україні n міст і 0 доріг. До 30-ої річниці незалежності пора б це виправити.
Ви хочете побудувати n-1 дорогу між містами таким чином, щоб ними з кожного міста можна було дістатись до будь-якого іншого. Вартість прокладання дороги між містами i та j рівна (a_i + a_j)\bmod M мільйонів гривень з бюджетних коштів, де M — улюблене число чинного Президента України.
Яку найменшу кількість мільйонів гривень з бюджетних коштів потрібно витратити для виконання цього плану?
Input data
Перший рядок містить два цілих числа n, M (1 \le n \le 200000, 1 \le M \le 10^9) — число міст та улюблене число чинного Президента України відповідно.
Другий рядок містить n цілих чисел a_1, a_2, \ldots, a_n (0 \le a_i < M).
Output data
Виведіть найменшу кількість мільйонів гривень з бюджетних коштів, які потрібно витратити, щоб побудувати n-1 дорогу, щоб ними з кожного міста можна було дістатись до будь-якого іншого.
Examples
3 350 42 69 300
130
12 12 3 7 5 2 9 7 6 7 8 7 2 1
14
6 11 3 2 2 2 2 8
17
1 998244353 7788
0
Note
В першому прикладі ми можемо прокласти 3 дороги з наступними вартостями:
Між містами 1, 2: (42 + 69)\bmod 350 = 111
Між містами 1, 3: (42 + 300)\bmod 350 = 342
Між містами 2, 3: (69 + 300)\bmod 350 = 19
Найвигідніше обрати дороги (1, 2) та (2, 3), з сумарною вартістю 111+19 = 130.