HASTOCK - B - Stock Charts
题意翻译
**一句话题意**
给出$N$条**折线段**，求出最少分多少组使得每组的折线段都不互相相交。
$1 \le T \le 100$，$2 \le k \le 25$，$0 \le price_i \le 1000000$，$1 \le n \le 16$
**输入格式**
第一行给出数据总组数$T$。
对于每组数据，首先给出$n$和$k$，表示有$n$条折线段，然后以下$n$行，每行$k$个数($price_1,price_2,...,price_k$)，表示该折线横坐标为$1,2,...,k$时的纵坐标的值。
**输出格式**
对于每组数据，输出最少的分组数。
**样例输入**
```
3
3 4
1 2 3 4
2 3 4 6
6 5 4 3
3 3
5 5 5
4 4 6
4 5 4
5 2
1 1
2 2
5 4
4 4
4 1
```
**样例输出**
```
Case #1: 2
Case #2: 3
Case #3: 2
```
题目描述
**B - Stock Charts**
You're in the middle of writing your newspaper's end-of-year economics summary, and you've decided that you want to show a number of charts to demonstrate how different stocks have performed over the course of the last year. You've already decided that you want to show the price of **n** different stocks, all at the same **k** points of the year.
A _simple chart_ of one stock's price would draw lines between the points (0, price $ _{0} $ ), (1, price $ _{1} $ ), ... , (k-1, price $ _{k-1} $ ), where price $ _{i} $ is the price of the stock at the _i_th point in time.
In order to save space, you have invented the concept of an _overlaid chart_. An overlaid chart is the combination of one or more simple charts, and shows the prices of multiple stocks (simply drawing a line for each one). In order to avoid confusion between the stocks shown in a chart, the lines in an overlaid chart may not cross or touch.
Given a list of _n_ stocks' prices at each of _k_ time points, determine the minimum number of overlaid charts you need to show all of the stocks' prices.
Input
The first line of input will contain a single integer **T**, the number of test cases. After this will follow **T** test cases on different lines, each of the form:
```
n k
price0,0 price0,1 ... price0,k-1
price1,0 price1,1 ... price1,k-1
...
pricen-1,0 pricen-1,1 ... pricen-1,k-1
```
Where price $ _{i,j} $ is an integer, the price of the _i_th stock at time _j_.
Output
For each test case, a single line containing "Case #X: Y", where _X_ is the number of the test-case (1-indexed) and _Y_ is the minimum number of overlaid charts needed to show the prices of all of the stocks.
Limits
1 T 2 k 0
1 n
Sample
Input
Output
` 3<br></br> 3 4<br></br> 1 2 3 4<br></br> 2 3 4 6<br></br> 6 5 4 3<br></br> 3 3<br></br> 5 5 5<br></br> 4 4 6<br></br> 4 5 4<br></br> 5 2<br></br> 1 1<br></br> 2 2<br></br> 5 4<br></br> 4 4<br></br> 4 1<br></br>` ` Case #1: 2<br></br> Case #2: 3<br></br> Case #3: 2`