바부시카와 피에로기

바부시카 바이트미와(Babushka Bajtmiła)가 파티를 연다. 메인 요리는 그녀의 유명한 피에로기다.

파티에는 접시 $n$개가 있다. 바부시카는 $i$번째 접시에 정확히 $p_i$개의 피에로기를 올리려 한다. 모든 $p_i$는 서로 다르다. 그녀는 피에로기를 모두 만들어 $(p_1, \ldots, p_n)$개씩 $n$개 접시에 나누어 담았지만, 접시 순서를 뒤섞고 말았다.

바이트미라는 지쳐 있어서 연산 한 종류만 쓸 수 있다. 접시 $i$와 $j$를 골라 두 접시의 피에로기 수를 서로 바꾼다. 접시 $i$에 $x$개, 접시 $j$에 $y$개가 있으면 연산 후 접시 $i$에는 $y$개, 접시 $j$에는 $x$개가 놓인다. 이 연산은 $|x-y|+C$초가 걸린다. $C$초는 적당한 숟가락을 찾는 시간이고, 옮기는 피에로기 하나마다 1초가 더 든다.

파티가 곧 시작된다. 바이트미라는 부엌의 아무것도 건드리지 말라고 했지만, 당신의 알고리즘 실력을 믿는다. 접시의 순서를 원래대로 되돌리는 연산 순서를 가장 짧은 시간에 찾아 보라. 바이트미라를 도와줄 수 있겠는가?

첫 줄에 테스트 케이스 수 $z$($1 \le z \le 1000$)가 주어진다. 각 테스트 케이스의 첫 줄에는 $n$과 $C$가 주어진다($1 \le n \le 200\,000$, $1 \le C \le 10^9$). 이어서 $n$개 줄에 $i$번째 접시의 현재 피에로기 수 $a_i$와 목표 개수 $p_i$가 주어진다($1 \le a_i, p_i \le 10^9$).

각 테스트 케이스에서 $a_i$는 모두 다르며, 집합 $\{a_1, \ldots, a_n\}$과 $\{p_1, \ldots, p_n\}$은 같다. 모든 테스트 케이스에 걸친 $n$의 합은 1,000,000을 넘지 않는다.

각 테스트 케이스마다 첫 줄에 총 시간 $S$와 연산 횟수 $K$를 출력한다. 이어서 $K$줄을 출력하는데, $k$번째 줄에는 두 정수 $x_k$와 $y_k$를 쓴다. 이는 $k$번째 연산이 접시 $x_k$와 접시 $y_k$의 피에로기 수를 서로 바꾼다는 뜻이다. 모든 연산을 마친 뒤 접시 $i$에는 정확히 $p_i$개의 피에로기가 있어야 한다.

수열 $(2,3,1,4)$를 $(4,2,1,3)$으로 바꿔 보자. 먼저 1번과 2번 접시를 바꾸면 $(3,2,1,4)$가 되며, 비용은 $|3-2|+2=3$이다. 다음으로 1번과 4번 접시를 바꾸면 $(4,2,1,3)$이 되며, 비용은 $|3-4|+2=3$이다. 총 비용은 6이고, 이것이 최소다.