Nhân dịp tết, Bananabread đã về quê ăn tết cùng với họ hàng của mình. Các anh em họ của Bananabread đã tạo ra một trò chơi để đố anh ấy.

Cho một bảng ~N \times M~, ô ở dòng thứ ~i~ và cột thứ ~j~ có giá trị là ~A_{i,j}~. Các anh em họ của Bananabread đã đưa cho anh ~k~ miếng domino ~2 \times 1~ để đặt lên bảng. Các miếng domino có thể xoay ngang hoặc dọc, tuy nhiên phải đặt sao cho không đè lên nhau. Họ đố Bananabread hãy đặt sao cho các ô được phủ bởi domino có tổng lớn nhất có thể.

Yêu cầu: Hãy giúp Bananabread xem là tổng lớn nhất đạt được có thể là bao nhiêu.

Input

Dòng đầu gồm ~3~ số nguyên là ~N,M,K~. ~(1\le N\le 4,1\le M\le 1000,1\le K \le \frac{N*M}{2})~

~N~ dòng tiếp theo, mỗi dòng gồm ~M~ số nguyên. ~(|A_{i,j}| \le 10^9)~

Output

Gồm ~1~ số nguyên là tổng lớn nhất đạt được

Scoring

Sample Input 1

3 5 4
5 6 -9 -3 8
8 4 5 -10 -2
1 0 -10 9 -1

Sample Output 1

37

Notes

Cách đặt tối ưu cho ví dụ trên: