Bài 4. Thu thập nhiều vàng nhất

Mô tả

Cho lưới n x m, mỗi ô chứa một số vàng không âm. Một người đi từ ô (1,1) tới ô (n,m), mỗi bước chỉ được đi sang phải hoặc xuống dưới.

Một lần đổi hướng là khi bước hiện tại khác hướng với bước ngay trước đó. Ví dụ: đang đi sang phải rồi chuyển sang xuống dưới thì tính là 1 lần đổi hướng.

Hãy tìm số vàng lớn nhất có thể thu được nếu đường đi có không quá k lần đổi hướng.

Input

• Dòng đầu ghi ba số nguyên n, m, k.
• n dòng tiếp theo, mỗi dòng gồm m số nguyên a[i][j].

Output

In ra tổng vàng lớn nhất có thể thu được.

Giới hạn

• 1 <= n, m <= 1000 nếu không có ghi chú khác.
• Dữ liệu bảo đảm phù hợp với kiểu 64-bit signed integer nếu bài yêu cầu tổng hoặc chi phí.

Subtask

• Subtask 1 (20%): n, m <= 15.
• Subtask 2 (30%): k = 0 hoặc k = 1.
• Subtask 3 (50%): 1 <= n, m <= 200, 0 <= k <= n + m.

Ví dụ

Input

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

Output

29