Cho một ma trận hai chiều kích thước \(N x 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.

Dữ liệu vào

• Dòng đầu chứa số nguyên dương N\(None\) \((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.

Dữ liệu ra

• 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.

Input 1

4
7 4 3
2 5 7
3 6 9
4 5 3

Output 1

26

Giải thích

• Dòng thứ nhất: chọn số 7
• Dòng thứ hai: chọn số 5 (không cùng cột với số 7)
• Dòng thứ ba: chọn số 9 (không cùng cột với số 5)
• Dòng thứ tư: chọn số 5 (không cùng cột với số 9)
• Tổng các số được chọn: 7 + 5 + 9 + 5 = 26