Kì nghỉ hè của Taro sẽ bắt đầu vào ngày mai và cậu bé đã quyết định lên kế hoạch cho kì nghỉ ngay từ bây giờ.

Kì nghỉ gồm \(N\) ngày. Ngày thứ \(i\), Taro sẽ chọn một trong các hoạt động sau:

• A: Bơi ở biển. Đạt được \(a_i\) điểm hạnh phúc.
• B: Bắt côn trùng trên núi. Đạt được \(b_i\) điểm hạnh phúc.
• C: Làm bài tập về nhà. Đạt được \(c_i\) điểm hạnh phúc.

Vì Taro dễ chán nên cậu bé không thể làm cùng một hoạt động trong 2 ngày liên tiếp trở lên.

Hãy tính điểm hạnh phúc lớn nhất mà Taro có thể đạt được.

Input

• Dòng đầu: Ghi số nguyên \(N\) (\(1 \leq N \leq 10^5\)).
• \(N\) dòng tiếp theo, mỗi dòng ghi \(3\) số nguyên \(a_i, b_i, c_i\) (\(1 \leq a_i, b_i, c_i \leq 10^4\)).

Output

• Ghi một số nguyên duy nhất là tổng điểm hạnh phúc lớn nhất mà Taro có thể đạt được.

Example

3
10 40 70
20 50 80
30 60 90

210

7
6 7 8
8 8 3
2 5 2
7 8 6
4 6 8
2 3 4
7 5 1

46