19464번 - King's Roads 다국어

King Byteasar wants to introduce an innovative road network in Byteland. There are $n$ cities in Byteland. There are $a_i$ citizens living in $i$-th city.

Initially, there are no roads in Byteland. The king wants to build several roads in such a way that all cities are connected (directly or indirectly). He also wants to minimize expenses on maintaining the roads.

Naturally, if a road connects populous cities, it is used more heavily and thus is more expensive to maintain. Formally, maintaining a road between cities $i$ and $j$ costs $a_i + a_j$ bytalers per year. However, if $a_i + a_j$ is at least $M$, the road is considered a national highway, and it brings revenue of $M$ bytalers per year from taxation (thus, the effective cost for this road is $a_i + a_j - M$ per year). Note that all $a_i$ are less than $M$.

Help King Byteasar find the minimum annual cost for maintaining a set of roads so that all cities become connected.

The first line of input contains two space-separated integers $n$ and $M$ ($1 \leq n \leq 200\,000$, $1 \leq M \leq 10^9$).

The second line contains $n$ space-separated integers $a_1$, $\ldots$, $a_n$ ($0 \leq a_i < M$).

Print one integer --- the minimum annual cost for maintaining a spanning set of roads in bytalers.