eolymp
bolt
Try our new interface for solving problems
Problems

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

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

Time limit 3 seconds
Memory limit 256 MiB

В Україні 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

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

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.

Author Anton Trygub