Downward Game

There are N rows, and each row contains three digits from 0 to 9. The game starts at one of the three cells in the first row and moves down one row at a time until the last row.

When moving to the next row, you may move to the cell in the same column or to a horizontally adjacent column. In other words, from the left cell you may move to the left or middle cell of the next row, from the middle cell you may move to any of the three cells of the next row, and from the right cell you may move to the middle or right cell of the next row.

The score is the sum of the numbers written in all visited cells. Given the board, find the maximum and minimum scores that can be obtained.

The first line contains an integer N (1 ≤ N ≤ 100,000). Each of the next N lines contains three integers separated by spaces. Each integer is between 0 and 9, inclusive.

Print the maximum score and the minimum score, separated by a space.