An Extremely Original Spanning Tree Problem#12856

An Extremely Original Spanning Tree Problem

3 seconds
256 megabytes
Very hard

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?

Input

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).

Output

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.

Examples

Example 1

Loading
Loading

Example 2

Loading
Loading

Example 3

Loading
Loading

Example 4

Loading
Loading

Note

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.