D. Vibe-Coded Problem
time limit per test
3 seconds
memory limit per test
256 megabytes
input
standard input
output
standard output

After reading about vibe coding from a source he trusted(or used to trust), Radwan laid off all his engineers and hired vibe coders. Two months later, he found out how big his mistake was, so he wants to hire new engineers.

There are $$$n$$$ software engineers working for $$$m$$$ companies. The company of engineer $$$i$$$ is $$$c_i$$$, and hiring this engineer costs $$$s_i$$$. When Radwan pays the engineer $$$s_i$$$, he leaves his old company and joins Radwan's.

Radwan's company currently has no engineers. He wants to hire some of those engineers so that after the hiring is finished, his company has strictly more engineers than each of the other $$$m$$$ companies.

Find the minimum total hiring cost needed to achieve this goal.

Input

The first line contains an integer $$$t$$$ ($$$1 \le t \le 100$$$) — the number of test cases.

The first line of each test case contains two integers $$$n$$$ and $$$m$$$ ($$$1 \le n,m \le 3000$$$) — the number of engineers and the number of other companies.

Each of the next $$$n$$$ lines contains two integers $$$c_i$$$ and $$$s_i$$$ ($$$1 \le c_i \le m$$$, $$$1 \le s_i \le 10^9$$$) — engineer $$$i$$$'s current company and hiring cost.

It is guaranteed that the sum of $$$n$$$ over all test cases does not exceed $$$3000$$$, and the sum of $$$m$$$ over all test cases does not exceed $$$3000$$$.

Output

For each test case, print one integer — the minimum total cost required.

Example
Input
1
3 2
1 100
1 300
2 250
Output
350
Note

In the sample, he hires the engineer from company $$$1$$$ whose cost is $$$100$$$ and the engineer from company $$$2$$$ whose cost is $$$250$$$. His company then has $$$2$$$ engineers, while companies $$$1$$$ and $$$2$$$ have $$$1$$$ and $$$0$$$ engineers, respectively. The total cost is $$$100+250=350$$$.