Có N khối đá hình hộp chữ nhật. 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 nhất.

Input

• Dòng đầu là số N (N<= 5000).
• N dòng sau, mỗi dòng ghi 3 số nguyên dương là kích thước một khối đá. Các khối đá được đánh số từ 1 theo trình tự xuất hiện trong file.

Output

• Gồm một số nguyên duy nhất là độ cao lớn nhất của tháp.

Sample Input

10  
138 217 190  
166 140 223  
159 155 144  
129 152 207  
203 245 148  
146 108 145  
164 102 116  
204 151 170  
141 123 143  
181 118 183

Sample Output

812