Binary Grid

Interview

Time limit1sMemory limit1024 MB

Summary

Find the largest binary number spelled by the digits along a right-or-down path from the top-left to the bottom-right of a 0/1 grid.

Level: Medium5 of 10
Topics: Dynamic programming, Greedy, Matrix
Solved: No attempts yet

Problem

Each cell of an $N \times N$ grid contains either $0$ or $1$ . Inseon starts at row 1, column 1 and moves to row $N$ , column $N$ . Inseon can move only one cell at a time, either right (toward increasing column number) or down (toward increasing row number).

Each time Inseon visits a cell, Inseon appends the digit written in that cell to the end of the string Inseon holds. For example, in the figure below, if Inseon starts at row 1, column 1 and moves right, then down, then right, the string Inseon holds is 1101.

When Inseon reaches row $N$ , column $N$ , Inseon reads the string as a binary number $M$ . For example, if the string is 1101, then $M=13$ . Find the maximum value of $M$ that Inseon can compute.

Input

The first line contains an integer $N$ , the size of the grid. ( $2 \leq N \leq 30$ )

Each of the next $N$ lines contains $N$ integers separated by spaces. Each integer is either $0$ or $1$ . The $j$ -th number on line $i+1$ is the value written in the cell at row $i$ , column $j$ .

Output

Print the maximum value of $M$ . The answer can exceed the range of a 32-bit integer.

Examples3

Example 1
Input
```
3
1 0 1
0 0 0
0 1 0
```
Expected output
```
20
```
Example 2
Input
```
2
1 0
0 1
```
Expected output
```
5
```

Example 3

Input

Expected output