Minimum Total Duration of Non-overlapping Events

You are given several test cases. For each test case, there are N events, each with a start time and an end time. Your task is to select exactly M events such that no two selected events overlap and the sum of their durations is minimized.

An event i is represented by a pair \( (s_i, e_i) \) where the duration is \( e_i - s_i \). Two events \( i \) and \( j \) are non-overlapping if and only if \( e_i \leq s_j \) or \( e_j \leq s_i \). You need to determine the minimum total duration possible by selecting exactly M non-overlapping events. It is guaranteed that a valid selection exists for each test case.

Note: All events are processed independently in each test case.

inputFormat

The input is given via stdin and follows this format:

T
N1 M1
s11 e11
s12 e12
... 
s1N1 e1N1
N2 M2
s21 e21
s22 e22
... 
...
NT MT
sT1 eT1
sT2 eT2
... 
sTN_T eTN_T

Where:

• T is the number of test cases.
• For each test case, the first line contains two integers: N (the number of events) and M (the number of events to select).
• The next N lines each contain two integers, the start time \( s_i \) and the end time \( e_i \) of an event.

outputFormat

For each test case, output the minimum total duration of the selected events on a new line via stdout.

If there are T test cases, the output should contain T lines.

## sample

2
4 2
1 5
2 6
4 7
6 8
3 2
1 3
2 5
4 6

6
4

</p>