Ninja's Training (DP on Grids)

Ninja's Training (DP on Grids)

Given daily activity points across three categories, maximize total points with no same activity on consecutive days.

Input format

The first line contains N. The next N lines contain 3 integers each (daily training options).

Output format

Print maximum total points; can't repeat the same activity on consecutive days.

Constraints

• Values fit in a 64-bit signed integer
• Trailing whitespace and a trailing newline are ignored by the judge

Read from stdin, write to stdout. Sample cases below show the exact format.

10
41 36 34
35 23 1
37 33 2
0 48 32
5 3 30
22 2 24
35 18 39
43 25 28
30 20 41
47 44 12

371

3
3 42 25
20 50 16
31 0 10

106