This problem is also provided by Mathias Kern aka gardengnome - our warmes thanks for it!
On your journey through the dimensions you come across the 3D Easter Bunnies. It’s great to have all three dimensions back – you feel right at home!
The bunnies invite you to join them in their favourite game "towers of choco-joy". Chocolate Easter eggs come in rectangular 3D gift boxes, and the challenge is to stack these boxes on top of each other and build the tallest Easter egg gift box tower. The winner can eat all the Easter eggs!!!
For each box size is described with width x depth x height, boxes can be rotated and there is unlimited supply
of boxes of every given size.
To ensure a tower is stable, you can only put a box A on top of another box B if the width and depth of box A are strictly smaller than the corresponding dimensions of box B.
For example, if you have boxes of sizes 1x2x3 and 4x5x6, you can put a box 1x2x3 (width x depth x height)
on top of a box 2x3x1 (a rotation of 1x2x3), which in fact you can put on top of box 4x5x6 which itself
sits on top of the most bottom box 5x6x4. Overall, your choco-tower has a height of 3+1+6+4 = 14.
The actual game includes about 100 different box sizes and their dimensions can be up to 1000.
Input data provides amount of box sizes (i.e. types) N in the first line.
Next N lines describe every available type of boxes (width, depth, height).
Answer should just tell the maximum possible height of the choco box tower.
Example #1:
input:
3
1 2 3
4 5 6
7 8 9
answer:
30
Example #2:
input:
5
10 9 6
6 9 8
7 4 9
2 5 1
1 4 10
answer:
41