시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
2 초 256 MB 2 2 2 100.000%

문제

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.

예제 입력 1

5 9
1 3 5 8 8

예제 출력 1

6