TopCoder

Thumb 100
Slamur
ICPC ended for me, but problems will be always with me)

User's AC Ratio

80.0% (24/30)

Submission's AC Ratio

32.0% (32/100)

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

2
3 20
6 7 7
1 8 9
7 9 2
1 1
5 2 7

Sample Output

18
no solution

Hints

在 Sample Input 的第一筆測資中
是以$ { 7 , 9 , 2 } $為高

在 Sample Input 的第二筆測資中
以$ { 5 , 2 , 7 } $為高 皆會超過限制$1$

翻牆是會被記小過的 (?

Problem Source

Problem Set by Ting.H
建國中學106學年度校隊選拔:初試pD

Subtasks

For Testdata: 0 ~ 2, Score: 36
For Testdata: 3 ~ 4, Score: 23
For Testdata: 3 ~ 6, Score: 29
For Testdata: 0 ~ 8, Score: 12
No. Time Limit (ms) Memory Limit (KiB) Output Limit (KiB)
0 1000 65536 65536
1 1000 65536 65536
2 1000 65536 65536
3 1000 65536 65536
4 1000 65536 65536
5 1000 65536 65536
6 1000 65536 65536
7 1000 65536 65536
8 1000 65536 65536