Thanh là một người rất thích đi du lịch, Thanh muốn đi khắp mọi nơi từ Bắc vào Nam và đợt này Thanh sẽ đi du lịch ở một hòn đảo tại Khánh Hòa.

Kì nghỉ của Thanh gồm ~n~ ngày, để phục vụ cho thú vui tao nhã của mình thì Thanh đã nghĩ ra 3 hoạt động để làm mỗi ngày đó là:

1. Đi bơi. Nếu Thanh đi bơi ở ngày thứ ~i~ thì độ vui mà Thanh nhận được ngày hôm đó là ~a_i~.
2. Bắt bọ. Nếu Thanh bắt bọ ở ngày thứ ~i~ thì độ vui mà Thanh nhận được ngày hôm đó là ~b_i~.
3. Xây lâu đài cát. Nếu Thanh xây lâu đài cát ở ngày thứ ~i~ thì độ vui mà Thanh nhận được ngày hôm đó là ~c_i~.

Do thời gian có hạn nên mỗi ngày Thanh chỉ được làm 1 trong 3 hoạt động trên. Vì là một người dễ chán nên Thanh sẽ không làm lại hoạt động mà mình đã làm ngày hôm trước. Bạn hãy giúp Thanh tính độ vui lớn nhất mà Thanh có thể nhận được trong ~n~ ngày nghỉ để kì nghỉ của Thanh được trọn vẹn nhé.

Input

• Dòng đầu gồm ~n~ (~1 \leq n \leq 10^5~), là số ngày trong kì nghỉ của Thanh.
• Dòng thứ ~i~ trong ~n~ dòng tiếp theo gồm ~a_i, b_i, c_i~ (~0 \leq a_i, b_i, c_i \leq 10^9~), lần lượt là độ vui vẻ Thanh nhận được nếu đi bơi, bắt bọ, xây lâu đài cát trong ngày thứ ~i~.

Output

• Một dòng chứa độ vui lớn nhất mà Thanh có thể nhận được sau ~n~ ngày nghỉ.

Giới hạn

• 25% số test: ~n = 2~.
• 25% số test: ~n \leq 10^5~, mọi ngày ~i~ độ vui khi nhận được đều là 0 (~a_i = 0~).
• 25% số test: ~n \leq 100~.
• 25% số test: ~n \leq 10^5~.

Example Test

Input 1

2
2 0 3
4 3 2

Output 1

6

Input 2

3
10 40 70
20 50 80
30 60 90

Output 2

210

Input 3

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

Output 3

46

Giải thích

Test 1:

• Cách tối ưu nhất là: xây lâu đài cát ở ngày thứ nhất, bắt bọ ở ngày thứ hai. Tổng độ vui nhận được là ~2 + 4 = 6~.

Test 2:

• Cách tối ưu nhất là: xây lâu đài cát ở ngày thứ nhất, xây lâu đài cát ở ngày thứ hai, xây lâu đài cát ở ngày thứ ba. Tổng độ vui nhận được là ~70 + 50 + 90 = 210~.

Test 3:

• Cách tối ưu nhất là: xây lâu đài cát -> đi bơi -> bắt bọ -> đi bơi -> xây lâu đài cát -> đi bơi -> bắt bọ. Tổng độ vui nhận được là ~8 + 8 + 5 + 7 + 8 + 3 + 7 = 46~.