Lịch Hoạt Động

Một kế hoạch kéo dài $N$ ngày. Trong mỗi ngày $i$, bạn phải chọn đúng một trong ba hoạt động $A,B,C$, nhận lần lượt $a_i,b_i,c_i$ điểm. Không được chọn cùng một hoạt động trong hai ngày liên tiếp. Hãy tối đa hóa tổng điểm sau toàn bộ kế hoạch.

Input

• Dòng đầu chứa số nguyên $N$.
• Trong $N$ dòng tiếp theo, dòng $i$ chứa ba số $a_i,b_i,c_i$.

Output

• In tổng điểm lớn nhất có thể đạt được sau $N$ ngày.

Constraints

• $1\le N\le 10^5$.
• $1\le a_i,b_i,c_i\le 10^4$ với mọi $i$.

Scoring

• Subtask $1$ ($50\%$ số điểm): $N\le 10$.
• Subtask $2$ ($50\%$ số điểm): Không có giới hạn bổ sung.

Example

4
8 3 5
6 9 4
7 2 10
5 11 6

38