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 sang 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\leq i, j\leq 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,\ldots,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 bên trái có tọa độ \((x_{sh},\ y_{sh}),\ h=1,2,\ldots,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.

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.

Input

• 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}\leq10^6),\ (i=1,2,\ldots,n;\ j=1,2,\ldots,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},\ldots,\ x_{sp},\ y_{sp}\) xác định \(p\) hình vuông trong phương án thứ \(s\ (s=1,2,\ldots,k)\).

Output

• 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

• Có \(25\%\) số test ứng với \(25\%\) số điểm của bài có \(n\leq50;\ k\leq50;\ p\leq5\);
• Có \(25\%\) số test khác ứng với \(25\%\) số điểm của bài có \(n\leq500;\ k\leq10^5;\ p=2\);
• Có \(25\%\) số test khác ứng với \(25\%\) số điểm của bài có \(n\leq500;\ k\leq10^5;\ p=3\);
• \(25\%\) số test còn lại ứng với \(25\%\) số điểm của bài có \(n\leq500;\ k\leq10^5;\ p\leq5\);

Ví dụ

Sample input

4 2 2 3
1 1 1 1
1 1 1 1
1 1 1 1
1 1 1 1
1 1 2 2 3 3
1 1 1 3 3 1

Sample output

12

Giải thích

Các hình vẽ dưới đây mô tả hai phương án giải thưởng trong ví dụ và tổng giá trị của giải thưởng trong mỗi phương án:

Đọc đề gốc tại đây: