Prolego™ – Qualification 2013

Énoncé¶

Vous possédez un jeu de N briques de dimensions (x_i, y_i, z_i), ainsi qu'une machine vous permettant de dupliquer des briques. Vous pouvez orienter les briques comme bon vous semble, et les empiler pour former une tour de briques. Cependant, pour que la construction soit stable, vous ne pouvez poser une brique i sur une brique j que si la base de la brique du dessus est strictement incluse dans la base de la brique du dessous : elles ont respectivement des dimensions a × b et a' × b' telles que (a < a' et b < b') ou (a < b' et b < a'). Quelle est la hauteur de la plus grande tour que vous pouvez construire ?

Entrée¶

L'entrée comprendra :

• un nombre N, le nombre de briques que vous avez au départ ;
• sur les N lignes suivantes, les dimensions de chaque brique (x_i, y_i, z_i).

Sortie¶

Vous afficherez en sortie :

• la hauteur de la plus grande tour que vous pouvez construire.

Contraintes¶

• 1 <= N <= 2 000
• 1 <= x_i, y_i, z_i <= 10 000 000
• La hauteur de la plus grande tour ne dépasse jamais 100 000 000