Minimum Cost – Land Acquisition: The government of India plans to build a road In a city. The government also plans to acquire some lands to start the construction. The program must accept an Integer matrix of size **N*N** representing the heights of the buildings (i.e., the number of storeys In each building) in the city. A positive value X in the matrix indicates that there is an X-storey building. A zero value in the matrix indicates the presence of land that cannot be acquired by the government.

The rules for road construction In the city are given below.

– The road always starts from the first row and ends at the last row.

– No more than one building In a row can be acquired by the government.

The cost to acquire an X-storey building is X. The government has decided to acquire the lands with the minimum cost **M**. The program must print the minimum cost M to acquire land for road construction in the given city as the output. **NOTE:** It is always possible to build a road In the given city.

**Input Format: **

The first line contains N.

The next N lines, each contains N Integers separated by space. **Output Format:**

The first line contains M.**Example Input/Output 1: **

Input:

4

0 0 2 0

1 3 4 5

5 0 7 0

8 1 2 3

Output:

11**Example Input/Output 2: **

Input:

3

1 2 0

4 3 1

5 2 1

Output:

4

```
n=int(input())
mat=[list(map(int,input().split())) for r in range(n)]
for r in range(1,n):
for c in range(0,n):
if mat[r][c]==0:
continue
building=[]
if c!=0 and mat[r-1][c-1]!=0:
building.append(mat[r-1][c-1])
if c!=n-1 and mat[r-1][c+1]!=0:
building.append(mat[r-1][c+1])
if mat[r-1][c]!=0:
building.append(mat[r-1][c])
if building:
mat[r][c]+=min(building)
else: mat[r][c]=0
print(min([i for i in mat[n-1] if i!=0]))
```