Cánh cửa thần kì Nobita tham gia một trò chơi do Doremon thiết kế. Trò chơi diễn ra trong một mê cung kích thước 𝑚 × 𝑛. Các hàng được đánh số từ 1 đến 𝑚, các cột được đánh số từ 1 đến 𝑛, ô nằm ở hàng 𝑖 cột 𝑗 là phòng (𝑖, 𝑗). Có một số phòng sẽ có cánh cửa thần kì. Nobita được phép xuất phát tại bất kì phòng nào ở hàng 1 và phải di chuyển về một phòng bất kì ở hàng 𝑚. Giả sư Nobita đang ở phòng (𝑖, 𝑗), mỗi bước Nobita có thể di chuyển và nhận điểm như sau:

• Nobita có thể di chuyển sang một trong ba phòng (𝑖 + 1, 𝑗 − 1), (𝑖 + 1, 𝑗), (𝑖 + 1, 𝑗 + 1);
• Nếu phòng (𝑖, 𝑗) có cánh cửa thần kì, Nobita có thể di chuyển đến bất kì một phòng nào khác cũng có cánh cửa thần kì, thậm chí chính phòng mà Nobita đang ở, tuy nhiên Doremon chỉ cho phép Nobita 𝐶 lần sử dụng cánh cửa thần kì;
• Cứ mỗi lần vào phòng (𝑖, 𝑗) Nobita sẽ được thưởng hoặc phạt một điểm là 𝑝𝑖𝑗 (~𝑝_{𝑖𝑗}~ ≥ 0 là thưởng, ngược lại ~𝑝_{𝑖𝑗}~ < 0 là bị phạt).

Yêu cầu: Cho bản đồ mê cung, hãy giúp Nobita di chuyển để đạt được nhiều điểm nhất.

Input

• Dòng đầu chứa ba số nguyên 𝑚, 𝑛, 𝐶;
• Tiếp theo là 𝑚 dòng, mỗi dòng chứa 𝑛 số nguyên 0 hoặc 1 mô tả các phòng trong mê cung có hay không có cánh cửa thần kì;
• Tiếp theo là 𝑚 dòng, mỗi dòng chứa 𝑛 số nguyên mô tả điểm thưởng phạt của các phòng trong mê cung. Các số có giá trị tuyệt đối không vượt quá 106.

Output

• Gồm một số là tổng điểm nhiều nhất mà Nobita đạt được.

VÍ DỤ:

INPUT

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

OUTPUT

4

• Subtask 1: 𝑚, 𝑛 ≤ 30; 𝐶 ≤ 30;
• Subtask 2: 𝑚, 𝑛 ≤ 1000; 𝐶 = 0;
• Subtask 3: 𝑚, 𝑛 ≤ 1000; 𝐶 ≤ 30;
• Subtask 4: 𝑚, 𝑛 ≤ 1000; 𝐶 ≤ ~10^9~.