Vacation

Source: AtCoder

Version: Phuoc Hung OJ Extended

Problem Statement

A vacation lasts $N$ days. Each day, choose exactly one of activities A, B, C and gain $a_i,b_i,c_i$ happiness respectively. The same activity cannot be chosen on consecutive days. Maximize total happiness.

Input

Line 1 contains $N$. Each of the next $N$ lines contains $a_i,b_i,c_i$.

Output

Print the maximum total happiness.

Subtasks

• Subtask 1 — 20 points: 1 <= N <= 15.
• Subtask 2 — 30 points: 1 <= N <= 2000.
• Subtask 3 — 50 points: 1 <= N <= 100000; 1 <= a_i,b_i,c_i <= 10000.

Examples

Input

3
10 40 70
20 50 80
30 60 90

Output

210

Explanation

Choose C on day 1, B on day 2, and C on day 3, for $70+50+90=210$.