Cho mảng hai chiều m hàng, n cột với các phần tử là các số nguyên. Thực hiện Q phép biến đổi trên mảng này, mỗi phép biến đổi mô tả bằng bộ 5 số nguyên (i_1,j_1,i_2,j_2,d) thể hiện việc tăng tất cả các phần tử trong hình chữ nhật con của mảng có ô góc trên-trái là (i_1,j_1) và ô góc dưới-phải là (i_2,j_2) lên d đơn vị.

Yêu cầu: Sau khi thực hiện các phép biến đổi, hãy tìm hình vuông kích thước k×k trên mảng có tổng lớn nhất

Input:

• Dòng 1: Chứa ba số nguyên dương m,n≤1000,1≤k≤min⁡(m,n)

• Dòng 2...m+1: Dòng i+1 chứa n số nguyên, số thứ j là giá trị ở ô (i,j). Giá trị này có trị tuyệt đối không vượt quá 10^3

• Dòng tiếp theo chứa số nguyên dương Q≤〖10〗^5

• Q dòng cuối cùng, mỗi dòng chứa 5 số nguyên i_1,j_1,i_2,j_2,d mô tả một phép biến đổi

Output:

Một số nguyên duy nhất là kết quả tìm được

Sample Input

3 3 2
1 1 1
1 1 1
1 1 1
1
2 2 3 3 -1

Sample Output

3

Giới hạn

Có 50% số test trong đó tất cả các số nguyên có giá trị tuyệt đối không vượt 100