Phần thưởng

Vinh là người thắng cuộc trong một cuộc thi "Tìm hiểu kiến thức vũ trụ" và được nhận các phần thưởng do công ty AZ tài trợ. Trên mỗi ô của một lưới kích thước $n\times n$ ô vuông có cạnh độ dài đơn vị, Ban tổ chức xếp một món quà. Các dòng của bảng được đánh số từ $1$ đến $n$, từ trên xuống dưới và các cột của bảng được đánh số từ $1$ đến $n$, từ trái qua phải. Ô nằm trên giao của dòng $i$ và cột $j$ được gọi là ô $(i,j)$ và món quà trên ô đó có giá trị là $a_{ij}$ $(1\le i,j\le n)$.

Ban tổ chức cho phép Vinh chọn một trong $k$ phương án nhận phần thưởng. Phần thưởng trong phương án thứ $s$ $(s=1,2,\dots ,k)$ được xác định như sau: Vinh được nhận các món quà trên các ô của lưới thuộc một trong $p$ hình vuông kích thước $r\times r$, trong đó hình thứ $h$ xác định bởi ô góc trên trái có tọa độ $(x_{sh},y_{sh})$, $h=1,2,\dots ,p$. Chú ý là các hình vuông này nằm trọn vẹn trong lưới và có thể có các hình vuông là giao nhau. Mỗi món quà chỉ được nhận một lần dù ô của nó thuộc nhiều hình vuông.

Yêu cầu: Hãy giúp Vinh chọn phương án nhận phần thưởng với tổng giá trị của các món quà nhận được là lớn nhất.

Dữ liệu vào

• Dòng thứ nhất chứa bốn số nguyên dương $n$, $k$, $r$, $p$;
• Dòng thứ $i$ trong số $n$ dòng tiếp theo chứa $n$ số nguyên dương, số thứ $j$ là $a_{ij}$ $(a_{ij}\le {10}^6)$, $(i=1,2,\dots ,n$; $j=1,2,\dots ,n)$;
• Dòng thứ $s$ trong số $k$ dòng tiếp theo chứa $2\times p$ số nguyên dương $x_{s1},y_{s1},x_{s2},y_{s2},\dots ,x_{sp},y_{sp}$ xác định $p$ hình vuông trong phương án thứ $s$ $(s=1,2,\dots ,k)$; hình vuông thứ $h$ gồm các ô $(i,j)$ với $x_{sh}\le i\le x_{sh}+r-1$ và $y_{sh}\le j\le y_{sh}+r-1$.

Dữ liệu ra

In ra một số nguyên duy nhất là giá trị lớn nhất của tổng giá trị các món quà mà Vinh có thể nhận được.

Ràng buộc

• $n\le 500$; $k\le {10}^5$; $p\le 5$; $r\le n$;
• $a_{ij}\le {10}^6$;
• Các hình vuông nằm trọn vẹn trong lưới.

Subtasks

• Subtask 1 ($25\%$ số test, $25\%$ số điểm): $n\le 50$; $k\le 50$; $p\le 5$;
• Subtask 2 ($25\%$ số test, $25\%$ số điểm): $n\le 500$; $k\le {10}^5$; $p=2$;
• Subtask 3 ($25\%$ số test, $25\%$ số điểm): $n\le 500$; $k\le {10}^5$; $p=3$;
• Subtask 4 ($25\%$ số test, $25\%$ số điểm): $n\le 500$; $k\le {10}^5$; $p\le 5$.

Ví dụ