Sau khi rời khỏi khu rừng rậm rạp với một đội hình Pokemon ưng ý, bầu trời đột ngột tối sầm lại, những đám mây đen kịt cuồn cuộn kéo đến mang theo sấm chớp rền vang, báo hiệu một cơn bão kinh hoàng sắp sửa trút xuống. Để bảo vệ những người bạn nhỏ của mình, Ash và Pikachu buộc phải chạy thục mạng tìm nơi trú ẩn và vô tình bước chân vào Hang Động Sấm Sét, một nơi tối tăm, ẩm thấp và chứa đựng vô vàn những truyền thuyết đáng sợ. Tương truyền rằng, sâu thẳm bên dưới tầng địa chất của hang động này chính là nơi an nghỉ và phục hồi năng lượng của Zapdos - một trong ba con chim huyền thoại mang sức mạnh chi phối sấm sét của tự nhiên.

Theo bản đồ ba chiều mà Pokedex vừa quét được, cấu trúc bên trong của hang động giống hệt như một ma trận lưới khổng lồ bao gồm \(M\) hàng và \(N\) cột trải dài tít tắp. Ban đầu, do sự hỗn loạn lúc chạy trốn cơn bão, Ash bị đẩy vào đứng ở ô tọa độ \((1, 1)\) nằm tận cùng góc trên bên trái của hang, và mục tiêu sinh tử của cậu lúc này là phải tìm đường di chuyển đến lối ra duy nhất nằm ở ô \((M, N)\) tại góc dưới cùng bên phải để hy vọng có cơ hội diện kiến Zapdos. Không may thay, địa hình trong hang vô cùng dốc và trơn trượt bởi những dòng nước ngầm rỉ ra từ vách đá, khiến cho ở mỗi bước đi, cậu chỉ có thể cẩn thận bước chân xuống dưới một ô hoặc di chuyển sang phải một ô để giữ thăng bằng.

Hang động này không hề yên bình; rải rác khắp các lối đi là những tinh thể điện từ phát sáng lập lòe do sự cộng hưởng từ Zapdos. Tại mỗi ô tọa độ \((i, j)\) trong hang động có chứa một chỉ số năng lượng \(C_{i,j}\) đặc trưng. Nếu \(C_{i,j}\) là một số dương, đó là một viên đá năng lượng nguyên thủy, tỏa ra hơi ấm kỳ lạ giúp hồi phục sinh lực và tăng cường sức chiến đấu của Pikachu lên đúng bằng giá trị \(C_{i,j}\). Tuy nhiên, nếu \(C_{i,j}\) là một số âm, đó lại là một cơn ác mộng thực sự: những cái bẫy mìn tĩnh điện vô hình do bọn xấu Team Rocket bí mật giăng sẵn để săn lùng các loài Pokemon hoang dã, nếu vô tình giẫm phải, toàn bộ cơ thể Pikachu sẽ bị giật tung, làm giảm sút sức mạnh đi một lượng tương đương với trị tuyệt đối của nó \(|C_{i,j}|\).

Rất may mắn, trước khi bắt đầu chuyến đi dài ngày này, người bạn đồng hành Misty đã tinh tế dúi vào tay Ash một chiếc túi nhỏ chứa \(K\) tấm thẻ "Giải Trừ" sử dụng công nghệ lượng tử siêu việt. Mỗi khi Ash bước chân vào một ô có chứa bẫy mìn tĩnh điện (\(C_{i,j} < 0\)), cậu có quyền lựa chọn rút ra và kích hoạt một tấm thẻ Giải Trừ; luồng sóng lượng tử từ tấm thẻ sẽ ngay lập tức vô hiệu hóa mạch điện của cái bẫy tại ô đó, khiến nó trở thành một ụ đất vô hại và không làm suy giảm bất kỳ chút sức mạnh nào của Pikachu (lúc này có thể coi như \(C_{i,j} = 0\)). Dù vậy, số lượng thẻ là có hạn và chặng đường phía trước lại quá dài, cậu không thể lãng phí chúng một cách bừa bãi. Bằng nhãn quan chiến thuật nhạy bén, bạn hãy vạch ra một lộ trình di chuyển tối ưu nhất và chỉ định rõ những lúc nào cần dùng thẻ, để khi Ash và Pikachu đặt chân đến đích ở ô \((M, N)\), tổng sức mạnh mà Pikachu có thể tích lũy được trong cơ thể là con số lớn nhất có thể, chuẩn bị sẵn sàng cho cuộc đụng độ lịch sử với Zapdos.

Input

• Dòng đầu tiên chứa ba số nguyên \(M, N, K\) (\(1 \le M, N \le 500\); \(0 \le K \le 10\)).
• \(M\) dòng tiếp theo, mỗi dòng chứa \(N\) số nguyên \(C_{i,j}\) (\(-10^9 \le C_{i,j} \le 10^9\)).

Output

• In ra một số nguyên duy nhất là tổng năng lượng tích lũy lớn nhất đạt được tại ô \((M, N)\).

Example

2 3 1
5 -10 2
-3 4 -1

8

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

29

2 2 2
-100 -100
-100 -100

-100

Scoring

• Subtask \(1\) (\(20\%\) điểm): \(1 \le M, N \le 20, K = 0\).
• Subtask \(2\) (\(30\%\) điểm): \(1 \le M, N \le 100, K \le 5\).
• Subtask \(3\) (\(50\%\) điểm): Không còn ràng buộc gì thêm.