Mua sắm

Hồng dự định mua lần lượt \(n\) mặt hàng, mỗi mặt hàng sẽ được mua ở đúng một trong ba siêu thị \(A, B, C\).

Siêu thị \(A\) không có chương trình tích điểm.
Hai siêu thị \(B\) và \(C\) có chương trình tích điểm độc lập nhưng cùng cơ chế sau:

Nếu khách hàng đã mua ở siêu thị đó \(t\) lần thì hiện có \(t\) điểm tại siêu thị đó.
Ở lần mua tiếp theo (lần thứ \(t+1\)) tại siêu thị đó, khách hàng được giảm đúng \(t\) đồng cho lần mua này, và số điểm tại siêu thị đó tăng lên thành \(t+1\).

Mặt hàng thứ \(i\) \((1 \le i \le n)\) có giá ở ba siêu thị lần lượt là \(x_i, y_i, z_i\) (tương ứng ở \(A, B, C\)).

Yêu cầu. Hãy chọn siêu thị để mua từng mặt hàng sao cho tổng số tiền phải trả là nhỏ nhất.

\InputFile

• Dòng đầu chứa số nguyên dương \(n\).
• \(n\) dòng tiếp theo, dòng thứ \(i\) chứa ba số nguyên dương \(x_i, y_i, z_i\).

Giới hạn: \(1 \le n \le 3000\), \(1 \le x_i, y_i, z_i \le 10^9\).

\OutputFile

• In ra một số nguyên là tổng tiền nhỏ nhất để mua đủ \(n\) mặt hàng.

\Scoring

• (30%) \(n \le 10\);
• (40%) \(n \le 200\);
• (30%) \(n \le 3000\).

\Examples
\beginexample
\exmp
5
5 5 9
7 8 5
9 9 5
9 9 5
6 6 9

22

\endexample

\Note
Điểm tích lũy tại \(B\) và \(C\) được tính riêng rẽ. Nếu đã mua ở \(B\) \(t\) lần thì lần mua tiếp theo ở \(B\) được giảm \(t\) đồng (tương tự cho \(C\)).

\endproblem