Khu vực mà Hồng ở có ba siêu thị, siêu thị A ở trung tâm và hai siêu thị B, C xa trung tâm. Vì xa trung tâm, nên mỗi siêu thị B, C đều có chương trình tích điểm để giảm giá khi mua hàng. Hiện tại, Hồng đang gặp một bài toán khó và muốn nhờ các anh chị tham gia kỳ thi Duyên Hải 2021 giải giúp.

Hiện tại, Hồng đang gặp một tình huống là có hình thức giống nhau. Cụ thể, nếu một khách hàng đã mua hàng ở một siêu thị ~t~ lần thì khách hàng có ~t~ điểm tích lũy tại siêu thị đó, khi khách hàng mua lần tiếp theo (lần thứ ~t + 1~), khách hàng sẽ được giảm ~t~ đồng trong lần mua đó và số điểm tích lũy tại siêu thị này được tăng lên thành ~t + 1~.

Hồng dự định mua lần lượt ~n~ mặt hàng, mỗi mặt hàng sẽ được mua ở một trong ba siêu thị A, B, C. Qua khảo sát, Hồng được biết mặt hàng thứ ~i~ (~1 \le i \le n~) có giá ở ba siêu thị A, B, C tương ứng là ~x_i, y_i, z_i~.

Yêu cầu: Cho các giá trị ~x_i, y_i, z_i~ (~1 \le i \le n~) là giá của ~n~ mặt hàng tương ứng ở ba siêu thị A, B, C, hãy giúp Hồng tìm cách mua hết ít tiền nhất.

Input

• Dòng đầu chứa số nguyên dương ~n~;
• Dòng thứ ~i~ (~i = 1, 2, ..., n~) trong ~n~ dòng tiếp theo chứa ba số nguyên dương ~x_i, y_i, z_i~ (~n \le x_i, y_i, z_i \le 10^9~).

Output

• Ghi một số nguyên là tổng số tiền ít nhất để mua được ~n~ mặt hàng.

Sample Input 1

5
5 5 9
7 8 5
9 9 5
9 9 5
6 6 9

Sample Output 1

22

Giải thích:

• Mặt hàng thứ nhất mua ở siêu thị B, phải trả 5 và có số điểm tích lũy tại siêu thị B là 1;
• Mặt hàng thứ hai mua ở siêu thị C, phải trả 5 và có số điểm tích lũy tại siêu thị C là 1;
• Mặt hàng thứ ba mua ở siêu thị C, phải trả ~5 - 1 = 4~ và có số điểm tích lũy tại siêu thị C là 2;
• Mặt hàng thứ tư mua ở siêu thị C, phải trả ~5 - 2 = 3~ và có số điểm tích lũy tại siêu thị C là 3;
• Mặt hàng thứ năm mua ở siêu thị B, phải trả ~6 - 1 = 5~ và có số điểm tích lũy tại siêu thị B là 2. Tổng số tiền phải trả là: ~5 + 5 + 4 + 3 + 5 = 22~.

Subtasks

• Có 30% số lượng test ứng với 30% số điểm thỏa mãn điều kiện: ~n \le 10~;
• Có 40% số lượng test khác ứng với 40% số điểm thỏa mãn điều kiện: ~n \le 200~;
• Có 30% số lượng test còn lại ứng với 30% số điểm thỏa mãn điều kiện: ~n \le 3000~.