John Snow has been recently appointed commander of the nights watch, And as his first task he needs to defend castle black against the wildlings army again.

Mance Rayder, commander of the wildlings has assembled a fierce army consisting of Giants, Thenns, Hornfoots, Ice-river clans, cave people each having different fighting abilities

John has built various towers in the area.

From a tower a cannon can be fired in all or some of the four direction(N,W,E,S) which destroys all enemies in its way until it is blocked by a wall or a tower.

John has only one shot before the sunrise so he want to cause maximum damage.

Your task is to help john assign directions (possibly all / none)  to shoot cannons for each tower such that total damage is maximized. However no two cannons should cross paths without any wall or tower in between.

John can also choose not to the shoot any cannons from any tower

All cannons are fired simultaneously.

Input

A grid of size N each position in grid can be

'#' wall

'T' tower

‘0’ denoting empty space

integer(1-9) denoting the ability of enemy

First line is N size of the grid

next n lines specifies the grid

Output

Out put a single integer- maximum possible damage in one shot.

Constraints

N<=500

number of cannons <= 200

Example

Input:
4
T000
1#T3
292T
9000
Output:
17

Input: 
4
T000
1003
292T
9000
 
Output:
16