题目描述

有 $n$ 个盘子，第 $i$ 个盘子当前有 $a_i$ 个饺子，目标是变成 $p_i$ 个饺子。所有 $a_i$ 两两不同，所有 $p_i$ 两两不同，且两个集合相同。

一次操作可以选择两个盘子 $i,j$，交换它们当前的饺子数量。若交换前两个盘子上分别有 $x,y$ 个饺子，则本次操作耗时 $|x-y|+C$。

请输出一种总耗时最小的操作序列。

输入格式

第一行整数 $z$ 表示测试组数。每组数据第一行两个整数 $n,C$。接下来 $n$ 行，每行两个整数 $a_i,p_i$。

输出格式

每组数据先输出两个整数 $S,K$，表示最小总耗时和操作次数。接下来 $K$ 行，每行两个整数 $x_k,y_k$，表示交换这两个位置。

数据范围

$1\le z\le1000$，$1\le n\le200000$，$1\le C\le10^9$，$1\le a_i,p_i\le10^9$，所有测试的 $n$ 之和不超过 $10^6$。

样例

输入：

1
4 2
2 4
3 2
1 1
4 3

一种正确输出：

6 2
2 1
4 1