Xây tháp Babylon

Người Babylon có \(n\) loại khối gạch hình hộp chữ nhật, mỗi loại có kích thước \((x_i, y_i, z_i)\) và số lượng không giới hạn. Mỗi khối có thể được đặt theo bất kỳ hướng nào, tức là chọn một trong ba kích thước làm chiều cao, hai kích thước còn lại là hai cạnh của mặt đáy.

Họ muốn dựng một tòa tháp cao nhất bằng cách chồng các khối lên nhau. Quy tắc: khối đặt phía trên phải có cả hai cạnh đáy đều nhỏ hơn hẳn hai cạnh đáy của khối phía dưới. Vì có thể xoay mặt đáy nên ta so sánh cạnh nhỏ với cạnh nhỏ và cạnh lớn với cạnh lớn. Chẳng hạn khối có đáy \(2 \times 3\) đặt được lên khối có đáy \(3 \times 5\), nhưng khối có đáy \(3 \times 5\) không đặt được lên khối có đáy \(2 \times 3\).

Hãy tính chiều cao lớn nhất của một tòa tháp có thể xây.

Input

Input gồm nhiều bộ test. Mỗi bộ test có dạng:

• Dòng đầu chứa số nguyên \(n\).
• \(n\) dòng tiếp theo, dòng thứ \(i\) chứa ba số nguyên \(x_i, y_i, z_i\).

Input kết thúc bằng một dòng chứa số \(0\) (dòng này không phải là một bộ test).

Output

Với mỗi bộ test, in ra một dòng chứa chiều cao lớn nhất của tòa tháp.

Constraints

• \(1 \le n \le 500\)
• \(0 \le x_i, y_i, z_i \le 10^9\)
• Số bộ test trong một file input không quá \(100\).

Sample Input

1
2 5 9
3
4 6 7
1 8 3
5 5 2
3
3 3 3
3 3 3
4 4 4
0

Sample Output

11
24
7

Explanation

• Bộ test 1: chỉ có một loại khối \((2, 5, 9)\) nhưng dùng được nhiều khối. Đặt khối có đáy \(5 \times 9\) (cao \(2\)) ở dưới và khối có đáy \(2 \times 5\) (cao \(9\)) ở trên, tổng chiều cao \(2 + 9 = 11\).
• Bộ test 3: hai khối lập phương cạnh \(3\) không xếp chồng lên nhau được vì cạnh đáy phải nhỏ hơn hẳn; xếp khối cạnh \(4\) ở dưới và một khối cạnh \(3\) ở trên, tổng \(7\).