Kì nghỉ hè của \(Kaninho\) bắt đầu vào ngày mai, và anh ấy quyết định lên kế hoạch ngay từ bây giờ

Kì nghỉ gồm \(N\) ngày. Với mỗi \(i(1\le i\le N)\), \(Kaninho\) sẽ chọn \(1\) trong \(3\) hoạt động dưới đây và thực hiện nó vào ngày thứ \(i\) :

• A: Đi bơi ở biển. Thu về \(a_i\) độ "hạnh phúc".

• B: Đi bắt sâu bọ ở trên núi. Thu về \(b_{i}\) độ "hạnh phúc".

• C: Làm bài tập về nhà. Thu về \(c_i\) độ "hạnh phúc".

Bởi vì \(Kaninho\) dễ dàng buồn chán, nên anh ấy không thể thực hiện hai hoạt động giống nhau trong \(2\) ngày (hoặc hơn) liên tiếp.

Tìm độ "hạnh phúc" lớn nhất mà \(Kaninho\) có thể đạt được.

Input

• Dòng thứ nhất chứa số nguyên \(N(1\le N\le 10^5)\)

• \(N\) dòng tiếp theo, mỗi dòng chứa \(3\) số nguyên \(a_i,b_i,c_i(1\le a_i,b_i,c_i\le 10^4)\)

Output

• In ra độ "hạnh phúc" lớn nhất cần tìm

Example

3
10 40 70
20 50 80
30 60 90

210