Macbeth

Time limit2sMemory limit512 MB

Summary

Given n time intervals and w witches, each witch predicts a chain of non-overlapping intervals, so find the maximum number of intervals coverable by w chains.

Level: Medium6 of 10
Topics: Intervals, Greedy, Dynamic programming
Solved: No attempts yet

Problem

Macbeth is a loyal follower of the king, and he has just fought well in a battle. Then he meets three witches. They predict that he is about to be promoted, and that he will become king after that. The promotion happens exactly as predicted, so Macbeth starts to believe that he is destined to be king. He and his wife go blind with ambition, murder the king, and murder almost everyone they see as a threat or a rival.

The witches held that much power over Macbeth because their prediction was right. Macbeth should have asked for more than one prediction and made their job harder. Predicting with a crystal ball is hard work. A ball is fussy about when it lets you predict a particular event, and some predictions take longer than others. Working out how to make the largest number of predictions together is a difficult task for the witches.

Every event comes with one time interval. To predict event $i$ , one witch has to look into her crystal ball for the whole interval $[s_i, t_i]$ while thinking about event $i$ only. So even when two events share the same interval, a single witch predicts only one of them. A witch who has predicted event $i$ can predict event $j$ next only when $t_i \le s_j$ . The witches coordinate so that the total number of predicted events is as large as possible.

Given $w$ witches, find the maximum number of events they can predict.

Input

The first line contains the number of data sets $K \ge 1$ . Then $K$ data sets follow, each in the format below.

The first line of a data set contains two integers $n$ and $w$ . $0 \le n \le 1000$ is the number of events and $1 \le w \le 10$ is the number of witches.

Each of the next $n$ lines contains two integers $s_i$ and $t_i$ describing one event ( $0 \le s_i < t_i \le 10^7$ ).

Output

For each data set, first print Data Set x: on a line by itself, where $x$ is the number of the data set counting from 1. On the next line print the maximum number of events the witches can predict.

Print one blank line after each data set.

Examples6

Example 1

Input

Expected output

Data Set 1:
5

Example 2
Input
```
1
0 5
```
Expected output
```
Data Set 1:
0
```
Example 3
Input
```
1
1 1
0 10000000
```
Expected output
```
Data Set 1:
1
```
Example 4
Input
```
1
3 1
0 5
5 10
10 15
```
Expected output
```
Data Set 1:
3
```

Example 5

Input

Expected output

Data Set 1:
3

Example 6

Input

Expected output

Data Set 1:
1

Data Set 2:
2

Data Set 3:
2