1. 

/**
* FWP, Ausgewählte Probleme aus dem ACM Programming Contest, WS10/11
* Problem: 437 - The Tower of Babylon
* Link: http://uva.onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&page=show_problem&category=6&problem=378&mosmsg=Submission+received+with+ID+8411197
*
* @author Manuel Hager
* @version 1.0, 11/18/2010
*
* Method : Ad-Hoc
* Status : Accepted
* Runtime: 1.152
*/

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.io.OutputStreamWriter;
import java.io.PrintWriter;
import java.util.ArrayList;
import java.util.Comparator;
import java.util.TreeSet;

public class Main
{
private final BufferedReader reader;
private final PrintWriter writer;;
private final TreeSet<Block> blockSet;
private int bestResult = 0;

public Main(BufferedReader reader, PrintWriter writer) {
this.reader = reader;
this.writer = writer;
this.blockSet = new TreeSet<Block>();
}

public void process() throws IOException {
String[] numbers;

for(int numberOfBlocks = Integer.parseInt(reader.readLine()), currentCase = 1;
numberOfBlocks > 0; numberOfBlocks = Integer.parseInt(reader.readLine()))
{
//clear old data.
blockSet.clear();
bestResult = 0;

for(int i = 0; i < numberOfBlocks; i++) {
numbers = reader.readLine().trim().split("\\s+");
addBlock(Integer.parseInt(numbers[0]), Integer.parseInt(numbers[1]), Integer.parseInt(numbers[2]));
}
//calculate and print out result.
builtUpGraph();
writer.printf("Case %d: maximum height = %d%n", currentCase++, bestResult);
}
}

private void addBlock(int a, int b, int c) {

if(a == b && b == c) { //cube
tryToAdd(a, a, a);
}
else if(a == b) { //square tube
tryToAdd(a, a, c);
tryToAdd(a, c, a);
}
else if(b == c) { //square tube
tryToAdd(a, b, b);
tryToAdd(b, b, a);
}
else { //cuboid
tryToAdd(a, b, c);
tryToAdd(a, c, b);
tryToAdd(b, c, a);
}
}

private void tryToAdd(int a, int b, int c) {
Block block = new Block(a, b, c);

if(blockSet.contains(block)) {
Block tmp = blockSet.ceiling(block);
tmp.high = tmp.high > c? tmp.high :c;
}
else {
blockSet.add(block);
}
}

private void builtUpGraph() {
if(blockSet.isEmpty())
return;

ArrayList<Block> tail = new ArrayList<Block>();
tail.add(blockSet.pollFirst());

for(Block newBlock : blockSet)
{
boolean isAdded = false;

for(Block start : tail) {
if(runThroughGraph(start, newBlock) && !isAdded) {
isAdded = true;
}
}
if(!isAdded) {
tail.add(newBlock);
}
}

for(Block start : tail) {
calcBestResult(start);
}
}

private static boolean runThroughGraph(Block curr, Block newBlock)
{
boolean sthFound = false;

for (Block next : curr.next) {
if (runThroughGraph(next, newBlock)) {
sthFound = true;
}
}

if(!sthFound) {
if (newBlock.width > curr.width && newBlock.lenght > curr.lenght) {
if (!curr.next.contains(newBlock)) {
curr.next.add(newBlock);
}
return true;
}
}

return sthFound;
}

private void calcBestResult(Block start) {
if(start.next.isEmpty()) {
start.val += start.high;
if(start.val > bestResult) {
bestResult = start.val;
}
}
else {
for(Block next : start.next) {
next.val = start.high + start.val;
if(next.val > bestResult) {
bestResult = next.val;
}
calcBestResult(next);
}
}
}

private static class Block implements Comparable<Block>
{
public final int lenght;
public final int width;
public int high;
public int val = 0;
public TreeSet<Block> next = new TreeSet<Block>();

public Block(int length, int width, int high) {
this.lenght = Math.min(length, width);
this.width = Math.max(length, width);
this.high = high;
}

@Override public boolean equals(Object obj) {
if(!(obj instanceof Block))
return false;

Block blockObj = (Block)(obj);
if(this.lenght == blockObj.lenght && this.width == blockObj.width)
return true;

return false;
}

@Override public String toString() {
return String.format("(%d, %d, %d)", this.lenght, this.width, this.high);
}

@Override public int compareTo(Block blockObj) {
if(this.lenght != blockObj.lenght)
return new Integer(this.lenght).compareTo(new Integer(blockObj.lenght));

return new Integer(this.width).compareTo(new Integer(blockObj.width));
}

public static Comparator<Block> GetComperator() {
return new Comparator<Block>() {
@Override public int compare(Block obj1, Block obj2) {
return obj1.compareTo(obj2);
}
};
}
}

public static void main(String[] args) throws IOException
{
BufferedReader reader = new BufferedReader(new InputStreamReader(System.in));
PrintWriter writer = new PrintWriter(new OutputStreamWriter(System.out));

new Main(reader, writer).process();

reader.close();
writer.close();
}
}