В Україні n міст і 0 доріг. До 30-ої річниці незалежності пора б це виправити.
Ви хочете побудувати n−1 дорогу між містами таким чином, щоб ними з кожного міста можна було дістатись до будь-якого іншого. Вартість прокладання дороги між містами i та j рівна (ai+aj)modM мільйонів гривень з бюджетних коштів, де M — улюблене число чинного Президента України.
Яку найменшу кількість мільйонів гривень з бюджетних коштів потрібно витратити для виконання цього плану?
Перший рядок містить два цілих числа n, M (1≤n≤200000,1≤M≤109) — число міст та улюблене число чинного Президента України відповідно.
Другий рядок містить n цілих чисел a1,a2,…,an (0≤ai<M).
Виведіть найменшу кількість мільйонів гривень з бюджетних коштів, які потрібно витратити, щоб побудувати n−1 дорогу, щоб ними з кожного міста можна було дістатись до будь-якого іншого.
В першому прикладі ми можемо прокласти 3 дороги з наступними вартостями:
Між містами 1, 2: (42+69)mod350=111
Між містами 1, 3: (42+300)mod350=342
Між містами 2, 3: (69+300)mod350=19
Найвигідніше обрати дороги (1,2) та (2,3), з сумарною вартістю 111+19=130.