Escape Room

Interview

Time limit1sMemory limit512 MB

Summary

On a grid of digits where 0 cells are walls, find two reachable cells whose shortest-path distance is maximum and report the largest sum of their digits, or 0 if none exists.

Level: Medium6 of 10
Topics: BFS, Graph, Brute force, Implementation
Solved: No attempts yet

Problem

You must escape an area surrounded by rooms. You can escape by entering the correct password.

The map of the area is an $N \times M$ grid, each cell is a room, and each cell contains a digit from 0 to 9, which is the number written in that room.

You can move only in the four directions up, down, left, and right, and you cannot enter a room with a 0 written on it.

The hints for the password are as follows.

When moving from any room to another room, you always move along a shortest path between the two rooms.
The sum of the numbers written on the start room and the end room of the longest path among the paths satisfying condition 1.

If multiple paths satisfy the two conditions above, the password is the largest sum of the numbers written on the start room and the end room.

The start room and the end room may be the same location.

Given a $5 \times 5$ map, the paths satisfying the two conditions above are as follows.

Find the password in this case.

If the password cannot be made, output 0.

Input

The first line gives the height $N$ ( $1 \le N \le 50$ ) and the width $M$ ( $1 \le M \le 50$ ) of the map, separated by a space.

From the second line, $N$ lines follow, each giving the information $A$ ( $0 \le A \le 9$ ) of the rooms, separated by spaces.

Output

Output the correct password.

Examples3

Example 1

Input

Expected output

Example 2
Input
```
2 2
1 2
3 4
```
Expected output
```
5
```

Example 3

Input

5 6
2 0 7 4 0 2
0 8 5 0 3 0
6 9 5 7 7 2
6 9 3 9 9 7
0 8 7 4 0 3

Expected output