THỰC HÀNH

Có N khối đá hình hộp chữ nhật đánh số từ 1 đến N. Khối thứ i có kích thước là a_i × b_i × c_i. Người ta muốn xây một cái tháp bằng cách chồng các khối đá này lên nhau. Để đảm bảo an toàn, các khối đá được đặt theo nguyên tắc:

• Chiều cao của mỗi khối là kích thước nhỏ nhất trong ba kích thước.
• Các mép của các khối đươc đặt song song với nhau sao cho không có phần nào của khối nằm trên bị chìa ra ngoài so với khối nằm dưới.

Hãy tìm phương án xây dựng để tháp đạt được độ cao lớn nhất.

Dữ liệu vào:

• Dòng đầu tiên là số N.
• N dòng tiếp, dòng thứ i ghi ba số a_i, b_i, c_i (hai số liên tiếp cách nhau một dấu cách).

Dữ liệu ra:

Một số nguyên duy nhất là độ cao lớn nhất của tháp xây được.

Ví dụ:

Dữ liệu vào:
9
7 5 5
4 4 8
1 1 5
4 2 2
5 1 5
4 2 7
2 9 2
1 3 3
5 5 5

Dữ liệu ra:
13

Giải thích: Dùng các khối đá số 1, 9, 5, 4 (théo thứ tự từ đáy tháp lên) với các kích thước đáy và chiều cao là:

Khối số 1: (5×7)×5

Khối số 9: (5×5)×5

Khối số 5: (5×5)×1

Khối số 4: (2×4)×2

Giới hạn: 1 ≤ N ≤ 5000; 1 ≤ a_i, b_i, c_i ≤ 1000.