eolymp
Competitions

2021-2022 ICPC, SEERC, 1/8 Final

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

В Україні $n$ міст і $0$ доріг. До $30$-ої річниці незалежності пора б це виправити. Ви хочете побудувати $n-1$ дорогу між містами таким чином, щоб ними з кожного міста можна було дістатись до будь-якого іншого. Вартість прокладання дороги між містами $i$ та $j$ рівна $(a_i + a_j)\bmod M$ мільйонів гривень з бюджетних коштів, де $M$ --- улюблене число чинного Президента України. Яку найменшу кількість мільйонів гривень з бюджетних коштів потрібно витратити для виконання цього плану? \InputFile Перший рядок містить два цілих числа $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$). \OutputFile Виведіть найменшу кількість мільйонів гривень з бюджетних коштів, які потрібно витратити, щоб побудувати $n-1$ дорогу, щоб ними з кожного міста можна було дістатись до будь-якого іншого. \Note В першому прикладі ми можемо прокласти $3$ дороги з наступними вартостями: \begin{itemize} \item Між містами $1$, $2$: $(42 + 69)\bmod 350 = 111$ \item Між містами $1$, $3$: $(42 + 300)\bmod 350 = 342$ \item Між містами $2$, $3$: $(69 + 300)\bmod 350 = 19$ \end{itemize} Найвигідніше обрати дороги $(1, 2)$ та $(2, 3)$, з сумарною вартістю $111+19 = 130$.
Time limit 3 seconds
Memory limit 256 MiB
Input example #1
3 350
42 69 300
Output example #1
130
Input example #2
12 12
3 7 5 2 9 7 6 7 8 7 2 1
Output example #2
14
Input example #3
6 11
3 2 2 2 2 8
Output example #3
17
Input example #4
1 998244353
7788
Output example #4
0
Author Anton Trygub