VOI 18 Bài 4 - Phần thưởng - VNOJ: VNOI Online Judge

VOI 18 Bài 4 - Phần thưởng

Điểm: 0,50 (OI)

Giới hạn thời gian: 1.0s

Giới hạn bộ nhớ: 256M

Input: stdin

Output: stdout

Dạng bài

Ngôn ngữ cho phép

C, C++, Go, Java, Kotlin, Pascal, PyPy, Python, Rust, Scratch

Trong trường hợp đề bài hiển thị không chính xác, bạn có thể tải đề bài tại đây: Đề bài

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

Vinh là người thắng cuộc trong một cuộc thi "Tìm hiểu kiến thức vũ trụ" và được nhận các phần thưởng do công ty AZ tài trợ. Trên mỗi ô của một lưới kích thước ~n \times n~ ô vuông có cạnh độ dài đơn vị, Ban tổ chức xếp một món quà. Các dòng của bảng được đánh số từ ~1~ đến ~n~, từ trên xuống dưới và các cột của bảng được đánh số từ ~1~ đến ~n~, từ trái qua phải. Ô nằm trên giao của dòng ~i~ và cột ~j~ được gọi là ô ~(i, j)~ và món quà trên ô đó có giá trị là ~a_{ij}~ ~(1 \le i, j \le n)~.

Ban tổ chức cho phép Vinh chọn một trong ~k~ phương án nhận phần thưởng. Phần thưởng trong phương án thứ ~s~ ~(s = 1, 2, \dots, k)~ được xác định như sau: Vinh được nhận các món quà trên các ô của lưới thuộc một trong ~p~ hình vuông kích thước ~r \times r~, trong đó hình thứ ~h~ xác định bởi ô góc trên trái có tọa độ ~(x_{sh}, y_{sh})~, ~h = 1, 2, \dots, p~. Chú ý là các hình vuông này nằm trọn vẹn trong lưới và có thể có các hình vuông là 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

Dòng thứ nhất chứa bốn số nguyên dương ~n~, ~k~, ~r~, ~p~;
Dòng thứ ~i~ trong số ~n~ dòng tiếp theo chứa ~n~ số nguyên dương, số thứ ~j~ là ~a_{ij}~ ~(a_{ij} \le 10^6)~, ~(i =1, 2, \ldots, n~; ~j = 1, 2, \ldots, n)~;
Dòng thứ ~s~ trong số ~k~ dòng tiếp theo chứa ~2 \times p~ số nguyên dương ~x_{s1}, y_{s1}, x_{s2}, y_{s2}, \ldots, x_{sp}, y_{sp}~ xác định ~p~ hình vuông trong phương án thứ ~s~ ~(s = 1, 2, \ldots, k)~.

Output

Ghi 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.

Giới hạn

Có ~25\%~ số test ứng với ~25\%~ số điểm của bài có ~n \le 50~; ~k \le 50~; ~p \le 5~;
Có ~25\%~ số test khác ứng với ~25\%~ số điểm của bài có ~n \le 500~; ~k \le 10^5~; ~p = 2~;
Có ~25\%~ số test khác ứng với ~25\%~ số điểm của bài có ~n \le 500~; ~k \le 10^5~; ~p = 3~;
~25\%~ số test còn lại ứng với ~25\%~ số điểm của bài có ~n \le 500~; ~k \le 10^5~; ~p \le 5~;

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

Note

Giải thích:

Các hình vẽ dưới đây mô tả 2 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:

Bình luận

Hãy đọc nội quy trước khi bình luận.

-4

tronghuy đã bình luận lúc 25, Tháng 12, 2023, 9:01

xin lỗi mn acc mình bị phá