1 #include <cstdio> 2 #include <cstring> 3 #include <algorithm> 4 #include <iostream> 5 using namespace std; 6 #define N 1000 7 struct Block{ 8     int x , y , h; 9 };10 11 bool cmp(const Block &a,const Block &b){12     if(a.x>b.x) return true;13     if(a.x==b.x&&a.y>b.y) return true;14     return false;15 }16 17 int k , dp[N];18 Block block[N];19 20 int main()21 {22   //  freopen("a.in" , "r" , stdin);23     int cas = 0;24     int n , a , b , h;25     while(~scanf("%d" , &n)){26         if(n == 0) break;27         k = 0;28         memset(dp,0,sizeof(dp));29         for(int i = 0 ; i < n ; i++){30             scanf("%d%d%d" , &a , &b , &h);31             block[k].x = a , block[k].y = b , block[k++].h = h;32             block[k].x = b , block[k].y = a , block[k++].h = h;33             block[k].x = a , block[k].y = h , block[k++].h = b;34             block[k].x = h , block[k].y = a , block[k++].h = b;35             block[k].x = b , block[k].y = h , block[k++].h = a;36             block[k].x = h , block[k].y = b , block[k++].h = a;37         }38 39         sort(block , block+k , cmp);40 41         for(int i = 0 ; i<k ; i++){42             dp[i] = block[i].h;43             for(int j = 0 ; j<=i ; j++){44                 if(block[i].x < block[j].x && block[i].y < block[j].y){45                     dp[i] = max(dp[i] , dp[j] + block[i].h);46                 }47             }48         }49 50         int maxn = 0;51         for(int i = 0 ;  i<k ; i++)52             maxn = max(maxn , dp[i]);53         printf("Case %d: maximum height = %d\n" , ++cas , maxn);54     }55     return 0;56 }