Cho bảng 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 trên giao của hàng i cột j gọi là ô (𝑖, 𝑗) trên ô đó chứa điểm thưởng là a_ij. (1 ≤ i ≤ m,1≤ j ≤ n).

Nam xuất phát tại một ô bất kì ở hàng 1 và phải di chuyển về một ô bất kì ở hàng thứ m. Nam có k phiếu may mắn. Khi Nam đang ở một ô may mắn, thì Nam có thể sử dụng hoặc không sử dụng phiếu may mắn để di chuyển. Giả sử Nam đang ở ô (𝑖, 𝑗), mỗi bước Nam có thể di chuyển như sau:

• Nam có thể di chuyển sang 3 ô: (𝑖 + 1, 𝑗 − 1), (𝑖 + 1, 𝑗), (𝑖 + 1, 𝑗 + 1);

• Nếu ô (𝑖, 𝑗) là ô may mắn thì:

  • Hoặc Nam không sử dụng phiếu may mắn, khi đó Nam có thể di chuyển sang 3 ô (𝑖 + 1, 𝑗 − 1), (𝑖 + 1, 𝑗), (𝑖 + 1, 𝑗 + 1);

  • Hoặc Nam sử dụng phiếu may mắn (nếu còn phiếu may mắn), khi đó số phiếu may mắn của Nam sẽ giảm đi 1, và Nam có thể di chuyển đến bất kì một ô khác cũng là ô may mắn, kể cả ô mà Nam đang đứng.

• Mỗi lần vào ô (𝑖, 𝑗), Nam sẽ được nhận được điểm thưởng là a_ij;

• Không được di chuyển ra ngoài bảng.

Yêu cầu: Hãy giúp Nam di chuyển từ một ô ở hàng 1 đến một ô ở hàng thứ m để đạt được tổng điểm lớn nhất.

INPUT

• Dòng đầu chứa ba số nguyên 𝑚, 𝑛, k;

• Dòng thứ i trong số m dòng tiếp theo chứa n số nguyên, số thứ j là d_ij với d_ij= 1 thì ô (i,j) là ô may mắn, d_ij= 0 thì ô (i,j) không là ô may mắn;

• Dòng thứ i trong số m dòng tiếp theo chứa n số nguyên, số thứ j là a_ij (|a_ij|≤〖10〗^6), là số điểm thưởng trên ô (i,j)

OUTPUT:

• Ghi một số là tổng điểm lớn nhất mà Nam đạt được.

Sample 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

Sample Output

4

Giới hạn

- Subtask 1: 𝑚, 𝑛 ≤ 30; k ≤ 30; 
- Subtask 2: 𝑚, 𝑛 ≤ 1000; k = 0; 
- Subtask 3: 𝑚, 𝑛 ≤ 1000; k ≤ 30; 
- Subtask 4: 𝑚, 𝑛 ≤ 1000; k ≤ 109.

```