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 each 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 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