Maximum Additional Seats

You are given an ( n \times n ) grid representing seats in a hall. Each cell in the grid is a seat: '0' indicates an empty seat while '1' indicates that the seat is already taken. Starting from the top-left corner and moving only to the right or downward, your goal is to find a path to the bottom-right corner consisting entirely of empty seats. The value of the path is defined as the number of seats (cells) along that path. If such a path exists, output the number of seats along the path (i.e. the maximum additional people that can be seated along that route); otherwise, output ( -1 ).

Note: Moves are restricted to rightward and downward steps only.

inputFormat

The input is read from standard input (stdin).

The first line contains an integer ( n ) representing the size of the grid. This is followed by ( n ) lines, each containing ( n ) space-separated characters. Each character is either '0' (an empty seat) or '1' (a taken seat).

outputFormat

Output a single integer to standard output (stdout): the number of seats along a valid path from the top-left to the bottom-right. If no such path exists, output ( -1 ).## sample

2
1 1
1 0

-1