겨울 숲의 수호자

야수들의 겨울 숲 습격이 시작되었다. 이를 맞아 겨울 숲의 수호자는 숲 상공에서 야수들에게 마법 화살을 쏘아 겨울 숲을 지키고자 한다.

습격이 시작된 시점부터 매 초마다 다음의 사건들이 순서대로 일어난다.

1. 현재 시점이 $a\_{i}$초일 경우 야수 $i$가 겨울 숲에서 $b\_{i}$만큼 떨어진 위치에 생성된다.
2. 살아 있는 모든 야수들 중, 겨울 숲에 아직 도착하지 않은 야수는 겨울 숲을 향해 $1$만큼 이동한다. 이미 겨울 숲에 도착해 있는 야수는 겨울 숲에 $1$의 피해를 입힌다.
3. 수호자는 살아 있는 야수 중 하나에 마법 화살을 쏜다. 발사된 화살은 야수를 즉시 타격할 수 있다. 한 야수가 화살을 맞은 총 횟수가 $K$번이 되었다면 그 야수는 죽는다.

수호자는 야수가 언제 어디서 생성될지 미리 알고 있으며, 이를 바탕으로 매 초마다 어떤 야수를 쏠지 전략을 잘 세우면 숲이 입는 피해를 줄일 수 있다.

예를 들어, 습격이 시작된 시점의 $0$초 후에 $20$만큼 떨어진 위치에서 야수 1이 등장하고, $1$초 후에 $14$만큼 떨어진 위치에서 야수 2가 등장하고 $K = 10$이라고 가정하자. 이 때 수호자가 야수 1을 $0$초부터 $10$번 공격하고 야수 2를 $10$초부터 $10$번 공격한다면, 야수 1은 겨울 숲에 다가오기 전에 죽지만 야수 2는 $15$초부터 겨울 숲을 공격하기 시작해서 $19$초까지 숲을 파괴하고 죽으므로 겨울 숲은 $5$의 피해를 입는다.

하지만 야수 1을 $0$초부터 $1$번, 야수 2를 $1$초부터 $10$번, 야수 1을 다시 $11$초부터 $9$번 공격하면 겨울 숲이 피해를 입지 않은 채로 모든 야수를 쓰러트릴 수 있다.

이 때 이러한 전략은 (시작 시간, 공격 횟수, 야수의 번호)로 나타내어지는 사건들이 시간 순서로 정렬된 집합으로 표현할 수 있다. 위의 예시에서 첫 번째 전략은 $(0, 10, 1)$, $(10, 10, 2)$로, 두 번째 전략은 $(0, 1, 1)$, $(1, 10, 2)$, $(11, 9, 1)$로 표현할 수 있다.

당신의 목적은 수호자를 도와 겨울 숲의 피해를 최소화하면서 모든 야수를 쓰러트리는 전략을 찾는 것이다.

첫 줄에 테스트 케이스의 수인 $T$ ($1 \leq T \leq 2,000$)이 주어진다.

각 테스트 케이스의 첫 줄에는 야수들의 수인 $N$ ($1 \leq N \leq 10,000$)과 야수 하나를 쓰러트리기 위해 쏴야 하는 화살의 수인 $K$ ($1 \leq K \leq 100,000$)이 주어진다.

다음 $N$개의 줄에 $i$번째 야수가 생성되는 시간인 $a\_{i}$과 위치인 $b\_{i}$ ($0 \leq a\_{i}, b\_{i} \leq 10^{9}$)가 주어진다.

모든 테스트 케이스들의 $N$의 합은 $10,000$을 넘지 않음이 보장된다.

각 테스트 케이스에 대해 수호자가 세운 최적의 전략을 다음과 같이 출력한다.

첫 줄에는 겨울 숲이 입는 총 피해의 최소값을 출력한다.

다음 줄에는 수호자가 세운 전략을 표현하는 사건의 개수 $M$ ($N \leq M \leq 10 \times N$)을 출력한다. 입력의 모든 경우에 대해, 이러한 사건의 개수가 $10 \times N$을 넘지 않는 전략이 항상 존재함이 보장된다.

다음 $M$개의 줄에는 사건의 시작 시간인 $L$, 시작 시간부터 연속해서 같은 야수를 공격한 횟수인 $D$와 공격한 야수의 번호인 $j$를 한 줄씩 시간 순서로 출력한다. ($0 \leq L \leq 10^{14}$, $0 < D \leq K$, $1 \leq j \leq N$)

가능한 방법이 여럿일 경우 그 중 아무거나 출력한다.