Một trung tâm phân loại hàng hóa tự động được mô hình hóa thành một bảng lưới kích thước ~M \times N~ ô (các hàng được đánh số từ ~1~ đến ~M~ từ trên xuống dưới, các cột được đánh số từ ~1~ đến ~N~ từ trái sang phải). Tại ô ~(i, j)~, hệ thống được trang bị một băng chuyền nâng có độ cao niêm yết là ~A_{i,j}~.

Một kiện hàng cần được vận chuyển từ ô xuất phát ~(1, 1)~ đến ô đích ~(M, N)~. Do thiết kế cơ khí của hệ thống, mỗi bước chuyển hàng từ ô ~(i, j)~ sang ô ~(i', j')~ bắt buộc phải tuân theo các quy tắc sau:

• Hướng di chuyển: Kiện hàng chỉ được di chuyển sang phải hoặc xuống dưới (hoặc cả hai), tức là ~i' \ge i~ và ~j' \ge j~;

• Thay đổi vị trí: Kiện hàng phải thực sự di chuyển sang vị trí mới, tức là ~(i', j') \ne (i, j)~;

• Độ chênh lệch độ cao: Độ cao của ô điểm đến phải lớn hơn độ cao của ô xuất phát ít nhất ~D~ đơn vị, tức là ~A_{i',j'} - A_{i,j} \ge D~.

Mỗi bước di chuyển từ ô ~(i, j)~ sang ô ~(i', j')~ tiêu tốn một mức năng lượng bằng khoảng cách Manhattan giữa hai ô, cụ thể: Chi phí = ~(i' - i) + (j' - j)~.

Yêu cầu: Hãy tính tổng chi phí năng lượng nhỏ nhất để di chuyển kiện hàng từ ô ~(1, 1)~ đến ô ~(M, N)~. Nếu không tồn tại lộ trình di chuyển hợp lệ, in ra ~-1~.

Input

• Dòng ~1~: Chứa ba số nguyên ~M~, ~N~ và ~D~ ~(1 \le M, N \le 1000; 1 \le D \le 10^9)~ lần lượt là số hàng, số cột của bảng lưới và độ chênh lệch độ cao tối thiểu.

• ~M~ dòng tiếp theo, dòng thứ ~i~ chứa ~N~ số nguyên ~A_{i,1}, A_{i,2}, \dots, A_{i,N}~ ~(1 \le A_{i,j} \le 10^9)~ thể hiện độ cao của các ô trong bảng lưới.

Output

Ghi ra một số nguyên duy nhất là tổng chi phí năng lượng nhỏ nhất tìm được. Nếu không thể di chuyển kiện hàng từ ~(1, 1)~ đến ~(M, N)~, ghi ra ~-1~.

Scoring

Sample Input 1

3 4 5
1 3 2 9
4 7 8 2
2 5 6 12

Sample Output 1

5

Sample Input 2

2 2 10
5 8
6 12

Sample Output 2

-1

Notes

Test 1: Lộ trình tối ưu là ~(1, 1) \rightarrow (2, 2) \rightarrow (3, 4)~, cụ thể:

• Đi từ ~(1, 1)~ đến ~(2, 2)~: ~A_{2,2} - A_{1,1} = 7 - 1 = 6 \ge 5~; Chi phí = ~(2 - 1) + (2 - 1) = 2~.

• Đi từ ~(2, 2)~ đến ~(3, 4)~: ~A_{3,4} - A_{2,2} = 12 - 7 = 5 \ge 5~; Chi phí = ~(3 - 2) + (4 - 2) = 3~.

Tổng chi phí = ~2 + 3 = 5~.

Test 2: Mọi đường đi từ ~(1, 1)~ đến ~(2, 2)~ đều có độ chênh lệch độ cao nhỏ hơn ~D = 10~, do đó không tồn tại lộ trình hợp lệ.