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:
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.
Input | Output |
---|---|
3 2 2 3 3 4 5 6 Copy
|
21 Copy
|