Block by Block

Little Min Likes playing the "block by block" very much,she always plays it day and night.There are N types of blocks,each them have own Length and width of the bottom block and its height,we should place one block on the top another to build a tower and maximum the tower's height.

Now we slight change in the next game.We place the blocks on the X-axis,every block has its begin coordinate si and end coordinate ei,which means the blocks' positions are stable on the X-axis,at the same time, its height is 1 unit.The i-th block can place on the top of j-th only when si >= sj && ei <= ej,then we will build one tower by the new rule.
However,little Min thinks it is too easy for her,now she wants to better use of the number of blocks and the height of the tower she built can't be more than H.that is to say,to build the tower with H high or less,the more blocks she use,the happier she is!
Note that two or more blocks can place on the same height except the bottom of the tower!
The sample will tells the details.

The first line contains an integer T, the number of test cases (T <= 20). Each test case is in the following format.
The first line starts with an integer N (1 <= N <= 300) denoting the number of Blocks and an integer H (1 <= H <= 10) denoting the highest height of the tower. Then following N lines, Each line contains two integer si and ei (0 < si < ei <= 500).

For each test case, print one line containing one integer S meaning the maximum number of blocks she can use to build one tower.

2
4 3
1 10
1 4
4 9
6 8
5 3
1 10
1 4
4 9
3 5
12 14

4
3

erriyue

HDU 3rd “Vegetable-Birds Cup” Programming Open Contest