Trò chơi được diễn ra trên một bảng chữ nhật với kích thước ~m~x~n~ (các hàng được đánh số từ ~1~ tới ~m~ từ trên xuống dưới, các cột được đánh số từ ~1~ tới ~n~ từ trái sang phải). Mỗi ô trên bảng thuộc ~1~ trong ~2~ loại:

• Loot: ô sẽ chứa một món quà có giá trị từ ~1~ tới ~5~, với cân nặng tương đương với giá trị.
• Savepoint: ô không chứa quà (được ký hiệu bởi số ~0~), người chơi có thể thả toàn bộ món qua đã gom được và tính điểm tích luỹ.

Người chơi sẽ bắt đầu đi từ một ô bất kỳ ở cột ~1~. Mỗi bước di chuyển, người chơi buộc phải đi sang cột bên phải, đi đến hàng không chênh lệch quá 1 với hàng ban đầu (Từ toạ độ ~[i, j]~, người chơi có thể di chuyển tới các toạ độ ~[i-1,j+1]~, ~[i,j+1]~, ~[i+1,j+1]~ và không thể đi ra khỏi biên của bảng).

Vì thể lực có hạn nên người chơi tại mỗi thời điểm chỉ có thể mang cân nặng không vượt quá ~k~. Nhưng bởi vì quá tham lam, nên người chơi sẽ luôn nhặt món qua ở mỗi ô đi đến được, vậy nên tìm Savepoint để thả quà và tính điểm tích luỹ rất quan trọng. Khi người chơi đi đến cột ~n~, trò chơi kết thúc và số quà còn lại trên người sẽ được tính vào điểm tích luỹ trước đó từ tất cả các Savepoint và tổng kết.

Yêu cầu

Cho bảng chữ nhật trò chơi. Hãy tìm ra con đường tốt nhất để người chơi có thể hoàn thành trò chơi (nếu mang quá nặng thì sẽ thua) với tổng giá trị quà tích luỹ được là cao nhất.

Input

• Dòng đầu tiên chứa 3 số nguyên dương ~m~, ~n~, ~k~ ~(m,n≤100, k≤500)~ cách nhau một dấu cách.
• ~m~ dòng sau, mỗi dòng chứa ~n~ số nguyên ~a_{ij}~ ~(0≤a_{ij}≤5)~ cách nhau một dấu cách. Số ~0~ biểu diễn Savepoint, còn lại biểu diễn giá trị món quà.

Output

Gồm 1 dòng duy nhất chứa tổng giá trị món quà tích luỹ được nếu có thể hoàn thành trò chơi, ngược lại in ra -1.

Sample Input

3 4 5
1 1 0 1
1 2 1 2
2 1 1 1

Sample Output

6

Sample Input 2

3 4 1
1 1 0 1
1 2 1 2
2 0 1 1

Sample Output 2

-1