2015
02-22

# 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).

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).

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

1. 学算法中的数据结构学到一定程度会乐此不疲的，比如其中的2－3树，类似的红黑树，我甚至可以自己写个逻辑文件系统结构来。