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 ô 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ừ đến , từ trên xuống dưới và các cột của bảng được đánh số từ đến , từ trái qua phải. Ô nằm trên giao của dòng và cột được gọi là ô và món quà trên ô đó có giá trị là .
Ban tổ chức cho phép Vinh chọn một trong phương án nhận phần thưởng. Phần thưởng trong phương án thứ đượ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 hình vuông kích thước , trong đó hình thứ xác định bởi ô góc trên trái có tọa độ . 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.
Dữ liệu vào:
Dòng thứ nhất chứa bốn số nguyên dương ;
Dòng thứ trong số dòng tiếp theo chứa số nguyên dương, số thứ là ;
Dòng thứ trong số dòng tiếp theo chứa số nguyên dương xác định hình vuông trong phương án thứ .
Hai số liên tiếp trên cùng dòng được ghi cách nhau bởi dấu cách.
Dữ iệu ra:
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.
