Along your daily walk to school, there is a long pavement tiled with concrete slabs. The pavement is three slabs wide and rather long (it always feels longer on the walk home). One day you discover that some irresponsible youth has written graffiti on all these slabs. On closer inspection, you notice that it's mathematical graffiti—each slab has been marked with an integer.
This time, curiosity does not get the better of you. Instead you decide to play a game with your friends on the way to school. The game is played as follows:
For example, the pavement below is three slabs wide and seven slabs long. The best possible score is 50, obtained by stepping in the corners shown.
Note that you may leave any number of slabs between steps, and in fact if all slabs have negative points associated with them, you can simply opt to step on no slabs and retain a score of 0.
After several days of playing this game with your friends and consistently losing, you decide to whip out your trusty laptop to secure your place as the high scorer. Your task is to determine the highest score that can be achieved on a graffitied pavement, given the length of the pavement and the numbers on each slab.
Your program must read from standard input. The first line of input will contain a single integer L, the length of the pavement.
Following this will be L lines in the form x y z, describing the numbers written on each of the three slabs in the given row. These three numbers will be given in order from the left side of the pavement to the right (as seen by a person who is walking), and they will all be integers between -100,000 and 100,000, inclusive.
Your program must write a single line to standard output. This line must contain a single integer, giving the largest possible score you can obtain from walking along the pavement. You are guaranteed that the answer will never exceed 2,000,000,000.
7 7 1 11 6 3 9 -4 -2 8 -8 -10 17 5 4 -3 -1 2 0 3 9 -3
The score for each input scenario will be 100% if the correct answer is written to the output file, and 0% otherwise.