Имеется бесконечное количество прямоугольных кирпичей размерами x[i]
× y[i]
× z[i]
, каждый из которых можно ставить на любую грань (размеры каких-то двух сторон будут размерами основания, размер третьей стороны - высотой).
Ваша задача написать программу, находящую максимальную высоту башни, которую можно построить из этих кирпичей. Один кирпич может быть поставлен на другой, если размеры основания верхнего кирпича строго меньше соответствующих размеров основания нижнего.
В первой строке записано количество типов кирпичей n (1 ≤ n ≤ 30), за которым следуют 3n целых чисел (n троек x[i]
, y[i]
, z[i]
), описывающих размеры каждого типа кирпичей (1 ≤ x[i]
, y[i]
, z[i]
≤ 65000).
Выведите одно число - максимальную высоту башни.