Bài 1. xyz

Nhóm \(n\) người bạn của Alice bị lạc vào không gian, hiện tại người thứ \(t\) (\(1 \le t \le n\)) ở tọa độ \((x_t, y_t, z_t)\). Alice muốn chia \(n\) người thành ba nhóm, mỗi nhóm ít nhất một người để hỗ trợ và liên lạc với nhau. Nhóm thứ nhất sẽ dùng chiều không gian \(x\) để liên lạc, do đó chi phí để thiết lập kênh liên lạc cho nhóm thứ nhất được tính bằng \(\max X - \min X\), trong đó \(\max X\) và \(\min X\) tương ứng là tọa độ \(x\) lớn nhất và nhỏ nhất trong những người được phân vào nhóm thứ nhất. Tương tự, nhóm thứ hai sẽ dùng chiều không gian \(y\) để liên lạc và chi phí thiết lập kênh liên lạc được tính bằng \(\max Y - \min Y\); chi phí cho nhóm thứ ba bằng \(\max Z - \min Z\). Alice chia nhóm để tổng chi phí thiết lập kênh liên lạc cho cả ba nhóm là nhỏ nhất.

Yêu cầu: Cho \(n\) tọa độ \(x_t, y_t, z_t\), hãy giúp Alice chia nhóm để tổng chi phí thiết lập kênh liên lạc cho cả ba nhóm là nhỏ nhất.

Input

• Dòng đầu chứa số nguyên dương \(n\).
• Dòng thứ \(t\) (\(1 \le t \le n\)) trong \(n\) dòng tiếp theo chứa ba số nguyên \(x_t, y_t, z_t\) (\(-10^9 \le x_t, y_t, z_t \le 10^9\)).

Output

• Ghi ra một dòng chứa một số nguyên là tổng chi phí nhỏ nhất để thiết lập kênh liên lạc cho cả ba nhóm.

Example

6
1 5 5
5 5 5
9 9 9
8 8 8
1 3 3
1 5 9

1

Scoring

• Có \(25\%\) số test ứng với \(25\%\) số điểm của bài thỏa mãn: \(n \le 10\).
• Có \(25\%\) số test khác ứng với \(25\%\) số điểm của bài thỏa mãn: \(n \le 20\).
• Có \(25\%\) số test khác ứng với \(25\%\) số điểm của bài thỏa mãn: \(n \le 40\).
• Có \(25\%\) số test còn lại ứng với \(25\%\) số điểm của bài thỏa mãn: \(n \le 100\).