Đi đến trường

Dima cần đi từ nhà đến trường trong thời gian ngắn nhất.

Thành phố Dima đang ở là một lưới hình chữ nhật kích thước $n\times m$. Mỗi ô $(i,j)$ trên lưới được mô tả bởi một số $a_{ij}$:

• Nếu $a_{ij}=-1$: ô bị chặn, không thể đi qua.
• Nếu $a_{ij}=0$: ô trống, có thể đi qua.
• Nếu $a_{ij}=x$ với $1\le x\le {10}^9$: ô chứa một cổng dịch chuyển với chi phí $x$. Ô có cổng cũng là ô có thể đi qua.

Từ một cổng bất kỳ, Dima có thể nhảy đến một cổng khác bất kỳ. Thời gian di chuyển từ cổng $(i,j)$ đến cổng $(x,y)$ bằng $a_{ij}+a_{xy}$ (tổng chi phí của hai cổng).

Ngoài ra, Dima có thể đi từ một ô đến một ô trống kề cạnh trong thời gian $w$. Dima có thể đi qua một ô có cổng mà không sử dụng cổng đó.

Ban đầu Dima ở ô $(1,1)$ (góc trên-trái), trường ở ô $(n,m)$ (góc dưới-phải). Hai ô này được đảm bảo là ô trống (không phải $-1$).

Hãy tìm thời gian nhỏ nhất Dima cần để đi đến trường. Nếu không thể đến trường, in ra $-1$.

Dữ liệu vào

• Dòng đầu chứa ba số nguyên $n$, $m$, $w$ ($2\le n,m\le 2·{10}^3$; $1\le w\le {10}^9$).
• $n$ dòng tiếp theo, mỗi dòng chứa $m$ số nguyên $a_{ij}$ ($-1\le a_{ij}\le {10}^9$).

Dữ liệu ra

In ra một số nguyên duy nhất — thời gian nhỏ nhất để đi đến trường, hoặc $-1$ nếu không đến được.

Ràng buộc

• $2\le n,m\le 2·{10}^3$
• $1\le w\le {10}^9$
• $-1\le a_{ij}\le {10}^9$

Ví dụ