Going Down 2

Each of N lines holds three digits from 0 to 9. The going down game starts on the first line and ends on the last line.

You begin by choosing one of the three digits on the first line. After that you move down one line at a time, and a move goes to the cell directly below or to a cell horizontally next to the one directly below. From the left cell you move to the left cell or the middle cell of the next line, from the middle cell you move to any of the three cells, and from the right cell you move to the middle cell or the right cell.

The score is the sum of the digits in the cells you pass through. Given the table of digits, write a program that finds the largest score and the smallest score you can get.

The first line contains N ($1 \le N \le 100{,}000$). Each of the next N lines contains three digits separated by spaces. Each digit is one of 0 to 9.

On the first line, print the largest score and the smallest score, separated by a space.