Chọn số

Cho một ma trận hai chiều kích thước $N \times 3$ gồm $N$ dòng và 3 cột, mỗi dòng gồm 3 số nguyên dương $a_i, b_i, c_i$ ($i = 1..N$).

Yêu cầu: hãy chọn mỗi dòng một phần tử (không được phép chọn hai phần tử liên tiếp ở cùng một cột) sao cho tổng các phần tử được chọn trên $N$ dòng là lớn nhất.

Đọc từ tệp văn bản CHONSO.INP có cấu trúc:

• Dòng đầu chứa số nguyên dương $N$ ($1 \le N \le 10^5$);
• Dòng thứ $i$ ($i = 1..N$) trong $N$ dòng tiếp theo chứa 3 số nguyên dương $a_i, b_i, c_i$ ($a_i, b_i, c_i \le 10^7$);
• Các số nguyên trên một dòng được ghi cách nhau một khoảng trắng.

Ghi ra tệp văn bản CHONSO.OUT một số nguyên duy nhất biểu thị tổng các phần tử được chọn trên $N$ dòng là lớn nhất.

• Có 50% số điểm thỏa mãn điều kiện: $1 \le N \le 25$;
• Có 50% số điểm thỏa mãn điều kiện: $25 < N \le 10^5$.