맑은 하늘 프로젝트

2차원 세계를 지배하는 J. 왕국에 왕세자 H.가 태어났습니다! 국왕 M.은 이를 기념하여 2주일간의 축제 기간을 선포했습니다. 탄생 축제 기간의 마지막 날에는 거대한 축포를 쏘아 올려 J. 왕국의 모든 국민이 그 축포를 볼 수 있도록 할 예정입니다.

그러나 축포를 발사하기 전날, 국왕 M.은 걱정이 생겼습니다. 왕국 위에 떠 있는 수많은 구름이 문제였습니다. 축포가 구름에 가려 보이지 않으면 불운의 조짐으로 여겨질 것이고, 축제를 위해 수도를 찾은 사람들이 크게 실망할 것입니다.

고민 끝에 M. 왕은 대학생 시절 자취방의 제습제 대용으로 만들었던 "Nerdull-Nerdull-Han 레이저포(이하 너덜포)"를 꺼냈습니다. 희귀 금속 Nerdull로 만든 너덜포는 고출력의 매우 뜨거운 광선을 발사하기 때문에, 수증기 덩어리인 구름은 스치기만 해도 사라집니다. 다만 광선이 맞지 않으면 아무 일도 일어나지 않습니다. M. 왕은 이 문제를 다음과 같이 단순화할 수 있다고 직감했습니다.

1. 하늘에 있는 $N$개의 구름은 $x$축에 평행한 선분이다. 모든 구름은 $x > 0$인 영역에 있다.
2. 지면은 $y = 0$인 직선으로 보며, 너덜포는 지면 위의 한 지점에서 연직 위쪽으로 발사한다.
3. 내구도 문제 때문에 너덜포는 최대 $K$회까지만 발사할 수 있다.
4. 너덜포를 발사하면 고출력 광선이 지나는 경로 위의 모든 구름이 사라진다. 이때 필요한 전기 비용은 다음과 같다.

$\text{너덜포의 } x \text{ 좌표값 (= 발전소로부터 전력을 끌어오는 비용)} \times \text{사라지는 구름의 수}$

M. 왕은 이 문제를 쉽게 풀 수 있다고 생각했지만, 암산하는 도중에 H.가 울기 시작해서 계산을 당신에게 맡겼습니다. J. 왕국은 축제 기간 동안 예산을 많이 썼기 때문에, 구름을 제거하는 비용을 가능한 한 적게 들이고 싶어 합니다. 가능한 적은 예산을 계산해서 국왕 전하의 신임을 얻으세요.

모든 구름을 제거하는 일이 불가능한 경우는 없습니다. 왕세자 H.는 신의 축복 아래 태어났거든요!

첫 행에는 평행 세계의 개수 $T$가 주어집니다.

각 평행 세계마다 구름의 개수 $N$ ($1 \le N \le 500$)과 너덜포의 내구도 $K$ ($1 \le K \le 500$)를 나타내는 두 정수가 공백으로 구분되어 주어집니다. 그다음 $N$개의 행에는 $i$번째 구름의 양 끝 $x$좌표인 두 정수 $L_i$와 $R_i$가 공백으로 구분되어 주어집니다. ($1 \le L_i \le R_i \le 10\,000$)

각 평행 세계마다 J. 왕국의 최소 구름 제거 비용을 한 행에 하나씩 출력합니다.