Maximizing Skill Levels

Prof. Pang has 3 different skills: soda drinking, fox hunting, and stock investing. In each of the \(n\) days, he chooses one skill to practice. On day \(i\) (1 \(\le\) \(i\) \(\le\) \(n\)), if he practices Skill \(j\) (1 \(\le\) \(j\) \(\le\) 3), his level in that skill increases by \(a_{i,j}\). However, at the end of each day, every skill that was not practiced will "decay". Specifically, if a skill has not been practiced for \(k\) consecutive days (starting from day 1 or since its last practice), its current level is decreased by \(k\) (with the level never dropping below 0). For example, if Prof. Pang practices Skill 1 on day 1 and Skill 2 on day 2, then at the end of day 1, Skills 2 and 3 (which were not practiced) are both reduced by 1. At the end of day 2, Skill 1 (skipped on day 2) is reduced by 1 and Skill 3 (skipped on both days) is reduced by 2.

Prof. Pang wants to maximize the total of his three skill levels after \(n\) days. Compute the maximum possible sum achievable by choosing an optimal practice schedule.

inputFormat

The first line contains an integer \(n\) representing the number of days. The next \(n\) lines each contain three integers \(a_{i,1}\), \(a_{i,2}\), and \(a_{i,3}\) which are the amounts the corresponding skill levels increase when practiced on day \(i\).

outputFormat

Output a single integer indicating the maximum possible sum of the three skill levels after \(n\) days.

sample

2
1 2 3
4 5 6

3