Tuffaha owns a tourism agency. He currently has $n$ tourists.

The $i^{th}$ tourist wants to visit two museums, the cost of going to the first musem is $a_{i, 1}$ and the cost of going to the second is $a_{i, 2}$. However, Tuffaha can negotiate with each museum's owner to reduce the price.

The negotiation rules are as follows:

• The cost of each negotiation is $d$.
• After the negotiation, the new cost cannot be lower than the minimum cost given by a currently existing museum. For example, if the costs of the museums are $2, 5, 6, 7, 9$, none of the museums is allowed to reduce the cost to less than $2$.
• The tourist is not allowed to pay the same price for both museums.

Given $d$ and the costs of the museums that each tourist wants to go to, Find the minimum total cost of getting all the tourist to visit their museums.

Note that all the museums are different, and each tourist wants to go to a different pair of museums.

The first line of input contains two integers, $n$, the number of tourists ($1 \leq n \leq 3 \cdot 10^5$), and $d$, the cost of one negotiation ($0 \leq d \leq 10^9$).

$n$ lines follow. The $i^{th}$ line contains two integers, $a_{i, 1}$ and $a_{i, 2}$, the cost of the two museums that the $i^{th}$ tourist wants to visit ($1 \leq a_{i, 1}, a_{i, 2} \leq 10^9, a_{i, 1} \neq a_{i, 2}$).

Output a single integer $k$, the total cost of getting all the tourists to their museums.