Маємо нескінченну кількість прямокутних цеглин розмірами \(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\)).

Вихідні дані

Виведіть одне число - максимальну висоту вежі.

Вхідні дані #1

1
10 20 30

Відповідь #1

40

Вхідні дані #2

2
6 8 10
5 5 5

Відповідь #2

21