Tòa tháp khối hộp

Một kiến trúc sư muốn xếp các khối hộp chữ nhật thành một tòa tháp thật cao. Ông có \(n\) loại khối, khối loại \(i\) có ba kích thước \(x_i \times y_i \times z_i\), và mỗi loại có vô hạn khối để dùng. Ông được tự do xoay khối: bất kỳ mặt nào trong sáu mặt đều có thể làm mặt đáy, kích thước còn lại khi đó là chiều cao.

Điều kiện xếp chồng: hình chữ nhật đáy của khối trên phải nhỏ hơn hẳn hình chữ nhật đáy của khối dưới ở cả hai chiều. Nói cách khác, sau khi sắp mỗi đáy thành cặp (cạnh ngắn, cạnh dài) thì cạnh ngắn của khối trên phải nhỏ hơn hẳn cạnh ngắn của khối dưới, và cạnh dài của khối trên phải nhỏ hơn hẳn cạnh dài của khối dưới.

Tính tổng chiều cao lớn nhất của một tòa tháp.

Input

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

• Dòng đầu là số nguyên \(n\).
• \(n\) dòng sau, mỗi dòng gồm ba số nguyên \(x_i, y_i, z_i\).

Số \(n = 0\) đánh dấu kết thúc input (không phải là một bộ test).

Output

Với mỗi bộ test in ra một dòng là chiều cao tối đa của tòa tháp.

Constraints

• \(1 \le n \le 16000\)
• \(0 \le x_i, y_i, z_i \le 10^9\)
• Tổng các giá trị \(n\) trong một file input không vượt quá \(10^5\).

Sample Input

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

Sample Output

11
14
12

Explanation

• Bộ 1: đặt khối có đáy \(4 \times 8\) (cao \(3\)) ở dưới và khối có đáy \(3 \times 4\) (cao \(8\)) ở trên: \(3 + 8 = 11\).
• Bộ 2: đặt khối \((5,7,9)\) có đáy \(7 \times 9\) (cao \(5\)) ở dưới, rồi khối \((5,7,9)\) có đáy \(5 \times 7\) (cao \(9\)) lên trên: \(5 + 9 = 14\).
• Bộ 3: các khối lập phương cạnh \(6\), \(4\), \(2\) chồng dần: \(6 + 4 + 2 = 12\) (hai khối cạnh \(4\) không thể chồng lên nhau).