Babushka and her pierogi

Babushka Bajtmiła is throwing a party! The main dish is her famous pierogi.

There are $n$ plates at the party. Babushka plans to put exactly $p_i$ pierogi on the $i$-th plate, and all the $p_i$ values are distinct. She prepared all the pierogi and divided them among the $n$ plates as $(p_1, \ldots, p_n)$, but then she mixed up the order of the plates.

Bajtmiła is tired and will only perform one kind of operation. She chooses two plates $i$ and $j$ and swaps the amounts of pierogi on them. If plate $i$ holds $x$ pierogi and plate $j$ holds $y$, then afterwards plate $i$ holds $y$ and plate $j$ holds $x$. This operation takes $|x - y| + C$ seconds: $C$ seconds to find a proper spoon, plus 1 second for each pierogi moved.

The party starts soon. Bajtmiła will not let you touch anything in the kitchen, but she trusts your algorithm. Find a sequence of operations that restores the desired order in the shortest possible time. Can you help Bajtmiła?

The first line contains the number of test cases $z$ ($1 \le z \le 1000$). Each test case starts with a line containing $n$ and $C$ ($1 \le n \le 200\,000$, $1 \le C \le 10^9$). The next $n$ lines each contain $a_i$ and $p_i$ ($1 \le a_i, p_i \le 10^9$), the current and desired amounts on the $i$-th plate.

In each test case, the values $a_i$ are distinct, and the sets $\{a_1, \ldots, a_n\}$ and $\{p_1, \ldots, p_n\}$ are equal. The sum of $n$ over all test cases does not exceed $1\,000\,000$.

For each test case, print two integers $S$ and $K$: the total time and the number of operations. Then print $K$ lines. The $k$-th line contains two integers $x_k$ and $y_k$, meaning the $k$-th operation swaps the amounts on plates $x_k$ and $y_k$. After all operations, plate $i$ must contain exactly $p_i$ pierogi.

The sequence $(2,3,1,4)$ should become $(4,2,1,3)$. First swap plates 1 and 2, which gives $(3,2,1,4)$ at cost $|3-2|+2=3$. Then swap plates 1 and 4, which gives $(4,2,1,3)$ at cost $|3-4|+2=3$. The total cost is $6$, and this is the minimum.