1993 . 冰塊塔
TopCoder
Tags
Description
根據傳說，大陸人喜歡吃冰塊，但吃冰塊前他有一個習慣，就是將一顆一顆的冰塊向上疊，成為一座冰塊之塔。
而你聽說了這件事後，打算學習大陸人，就翻過校牆去便利商店買了不少冰塊回學校疊，而你希望能用所有你所買的冰塊疊出一座最高的冰塊塔。原本這是一個很簡單的問題，但如果你現在抬頭往上看，你就會看到……資訊教室的天花板！
相信你有衝動想拆了天花板來簡化這題題目，但你做不到。所以你只好在你的冰塊塔之高度不超過限制$h$的情況下，疊出最高的冰塊塔。順便提醒你一件事，如果你沒有用到所有的冰塊，大陸人就會駭進TIOJ讓你的程式WA喔！
Input Format
第一列包含一個正整數$t\leq 20$，代表下面的測試資料數量。
每筆測試資料一開始都包含兩個正整數$n \leq 10^ 3$ , $h \leq 10^ 5$，表示冰塊的數量及天花板的高度。
接著有$n$行，每行有三個正整數$x,y,z \leq 10^ 4$，表示冰塊的長寬高。
| 子任務（測資） | 額外限制 | 分數 |
| 1 (0~2) | $n \leq 14$ | 36 |
| 2 (3~4) | $n \leq 100$ , $h \leq 10^ 4$ | 23 |
| 3 (3~6) | $n \leq 200$ , $h \leq 5 \times 10^ 4$ | 29 |
| 4 (0~8) | 無 | 12 |
Output Format
針對每一筆測資，輸出冰塊塔的最大高度。
若無解，請輸出no solution。
Sample Input 1
2
3 20
6 7 7
1 8 9
7 9 2
1 1
5 2 7
3 20
6 7 7
1 8 9
7 9 2
1 1
5 2 7
Sample Output 1
18
no solution
no solution
Hints
在 Sample Input 的第一筆測資中
是以$ { 7 , 9 , 2 } $為高
在 Sample Input 的第二筆測資中
以$ { 5 , 2 , 7 } $為高 皆會超過限制$1$
翻牆是會被記小過的 (？
Problem Source
Problem Set by Ting.H
建國中學106學年度校隊選拔：初試pD
Subtasks
| No. | Testdata Range | Score |
|---|---|---|
| 1 | 0~2 | 36 |
| 2 | 3~4 | 23 |
| 3 | 3~6 | 29 |
| 4 | 0~8 | 12 |