You live in a dangerous neighbourhood. Each night you walk home, the path home consists of a N by 3 tiled path (N rows).

Recently there have been many murders, and the tiles have been stained with blood.

Your feet are large, each step you take on the path home will cover a 2 by 2 grid of tiles, gathering some of the blood that has been left on the tiles onto your boots.

To make things simpler, you have marked each tile with a number representing the amount of blood on the tile, the i-th row and j-th column having value a[i][j]. Each step will add an amount of blood onto your boots (equal to the sum of the 2×2 grid of the tiles you step on). Moreover, some tiles may have soap on them and such, which previous murderers have dropped whilst trying to clean up after themselves, these will have negative numbers representing how much they clean your boots. Once you step on a tile, to get home as quick as possible, you cannot step on the same tile again.

You are smart, you know that the more blood you gather onto your boots, the less likely people are to attack you. You wish to gather as much blood as possible onto your boots by the end of your journey across the pavement. Your legs are long and you can skip over as many tiles as you wish on your way home.

Given the values of all the tiles, determine the maximum amount of blood you can get on your boots.

NOTE: Should you take a step, it must cover a 2×2 grid of tiles, you can't have half a foot out of the path or otherwise.

Input

The first line contains a single integer n, the length of the path home.

The next N lines contain 3 integers each, representing the values of tiles that lead home.

1 <= N <= 100,000

-1,000,000,000 <= a[i][j] <= 1,000,000,000

Output

A single integer representing the maximum amount of you can pick up on your boots.

Example

Input:
7
7 1 11
6 3 9
-4 -2 8
-8 -10 17
5 4 -3
-1 2 0
3 9 -3

Output:
50