Problem #3: PokéCubes
Pokéballs sold in Pokémarts are round in shape, but Little Joseph wanted to be different from the rest. In his own home laboratory, he has come up with a new invention for catching Pokémon: Pokécubes!
However, as Little Joseph is a very sloppy person, all his Pokécubes are of different sizes and dimensions, and most of the times not cubes. Also, his Pokécubes are not as powerful as Pokéballs and can shrink into the cute marble-sized Pokéball for easy storage. Hence, Little Joseph is having problems carrying around all his Pokécubes in his bag.
One day, PokéMaster Hubert gave Little Joseph a great idea: Little Joseph can pack smaller Pokécubes into the big Pokécubes and thus would not take as much space. When packing his Pokécubes, he starts with the smallest Pokécube and puts it entirely inside a larger one. Then he takes that Pokécube and puts it inside another, and so on. Your task as a PokéProgrammer is to find out the largest number of Pokécubes that can be fit in this way.
Note that Little Joseph can set the inner Pokécube on any side inside the larger Pokécube. So Pokécube A might not fit inside Pokécube B in one orientation, but would in another. To simplify things, we’ll ignore thickness of the Pokécube sides. So, a 3 by 4 by 5 Pokécube will fit inside of another 3 by 4 by 5 Pokécube.
The first line of the input will be an integer n (n <= 50) representing the number of Pokécubes Little Joseph has, followed by n number of lines with three integers x, y and z representing the dimensions of the Pokécube.
A single line with an integer representing the maximum number of Pokécubes Little Joseph can pack in this way.
3 4 5
5 6 3
1 4 10
4 4 4
6 6 5