Un problema de árbol generador extremadamente original#12856

Un problema de árbol generador extremadamente original

3 segundos
256 megabytes
Muy difícil

En Ucrania hay ciudades y carreteras. Para el .º aniversario de la independencia ya es hora de arreglarlo.

Quieres construir n-1 carreteras entre las ciudades de modo que por ellas se pueda llegar desde cada ciudad a cualquier otra. El costo de construir una carretera entre las ciudades y es igual a (a_i + a_j)\bmod M millones de grivnas de fondos presupuestarios, donde es el número favorito del actual Presidente de Ucrania.

¿Cuál es la menor cantidad de millones de grivnas de fondos presupuestarios necesaria para llevar a cabo este plan?

Entrada

La primera línea contiene dos enteros , (1 \le n \le 200000, 1 \le M \le 10^9) — la cantidad de ciudades y el número favorito del actual Presidente de Ucrania, respectivamente.

La segunda línea contiene enteros a_1, a_2, \ldots, a_n (0 \le a_i < M).

Salida

Imprime la menor cantidad de millones de grivnas de fondos presupuestarios que hay que gastar para construir n-1 carreteras de modo que por ellas se pueda llegar desde cada ciudad a cualquier otra.

Ejemplos

Ejemplo 1

Loading
Loading

Ejemplo 2

Loading
Loading

Ejemplo 3

Loading
Loading

Ejemplo 4

Loading
Loading

Nota

En el primer ejemplo podemos construir carreteras con los siguientes costos:

  • Entre las ciudades , : (42 + 69)\bmod 350 = 111

  • Entre las ciudades , : (42 + 300)\bmod 350 = 342

  • Entre las ciudades , : (69 + 300)\bmod 350 = 19

Lo mejor es elegir las carreteras y , con un costo total de 111+19 = 130.