Attendance Assurance

Winson's Semester 2 has started, and he wants to make plans to ace his studies and win the Dean's "Most Locked In" award.

Semester 2 consists of $N$ days. On the $i$-th day, $1 \le i \le N$, Winson will choose exactly one of his four units to attend a lecture on:

• Unit A: gain $a_\text{i}$ knowledge points
• Unit B: gain $b_\text{i}$ knowledge points
• Unit C: gain $c_\text{i}$ knowledge points
• Unit D: gain $d_\text{i}$ knowledge points

Due to his dwindling attention span, Winson is unable to attend a lecture on the same unit two or more days in a row. That is, on the $i$-th day, where $1 < i \le N$, he cannot choose to attend the same lecture as he did on the $i-1$-th day.

Find the maximum total knowledge points that Winson can gain over the semester.

Input

The first line contains an integer $N$, the number of days in Semester 2. The following $N$ lines contain integers $a_i, b_i, c_i, d_i$, the number of knowledge points winson can gain by attending a unit's lecture on the $i$th day.

Output

Output the maximum total knowledge points that Winson can gain over the semester.

Constraints

• $1 \le n \le 10^5$
• $1 \le a_i, b_i, c_i, d_i \le 10^4$

Example 1

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

17

If Winson chooses to go to Unit D's lecture on the first day, unit C's lecture on the second day, then unit D's lecture on the third day, he will obtain 4 + 6 + 7 = 17 knowledge points.

Example 2

1
2102 2014 2004 2099

2102

Example 3

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

67