There are cities and roads in Ukraine. By the th anniversary of independence it is time to fix that.
You want to build n-1 roads between the cities so that one can get from every city to any other one along them. The cost of building a road between cities and equals (a_i + a_j)\bmod M million hryvnias of budget funds, where is the favourite number of the current President of Ukraine.
What is the smallest number of million hryvnias of budget funds needed to carry out this plan?
The first line contains two integers , (1 \le n \le 200000, 1 \le M \le 10^9) — the number of cities and the favourite number of the current President of Ukraine respectively.
The second line contains integers a_1, a_2, \ldots, a_n (0 \le a_i < M).
Print the smallest number of million hryvnias of budget funds that need to be spent to build n-1 roads so that one can get from every city to any other one along them.
Example 1
Example 2
Example 3
Example 4
In the first sample we can build roads with the following costs:
Between cities , : (42 + 69)\bmod 350 = 111
Between cities , : (42 + 300)\bmod 350 = 342
Between cities , : (69 + 300)\bmod 350 = 19
It is best to choose the roads and , with total cost 111+19 = 130.