Going Down 2

Time limit1sMemory limit512 MB

Summary

Given N rows of three digits, move down choosing reachable cells and report the maximum and minimum possible sum of the digits passed through.

Level: Easy3 of 10
Topics: Dynamic programming, Array
Solved: No attempts yet

Problem

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.

Input

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.

Output

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

Examples2

Example 1
Input
```
3
1 2 3
4 5 6
4 9 0
```
Expected output
```
18 6
```
Example 2
Input
```
1
0 5 9
```
Expected output
```
9 0
```