Matej dự định mua mảnh đất hình chữ nhật có kích thước \(r×s\), mỗi ô đất ~(i,j)~ có giá ~c_{i,j}~. Trước khi mua, Matej đã tham khảo ý kiến của chuyên gia phong thủy và nhận được hai con số ma thuật ~a~ và ~b~. Matej chỉ được mua một vùng đất (bao gồm các ô đất nằm kề nhau) sao cho tổng giá trị chênh lệch của giá vùng đất và hai con số ma thuật là nhỏ nhất có thể.
Hay nói cách khác, với vùng đất từ ô ~(u,l)~ đến ô ~(d,r)~, gọi ~S~ là tổng giá trị các ô nằm trong vùng đất đó. Yêu cầu xác định giá trị nhỏ nhất của ~|S-a|+|S-b|~.
Input
Dòng đầu tiên chứa các số nguyên ~r~, ~s~, ~a~ và ~b~~(1 \le r,s \le 500; \; 1 \le a,b \le 10^9)~.
~r~ dòng tiếp theo, dòng thứ ~i~ chứa ~s~ số nguyên ~c_{i,j}~~(1 \le c_{i,j} \le 10^9)~.
Output
In ra giá trị tổng chênh lệch nhỏ nhất.
Samples
Sample Input 1
2 2 10 10
1 3
4 1
Sample Output 1
2
Sample Input 2
3 2 3 4
1 9
1 1
8 1
Sample Output 2
3
Sample Input 3
3 4 5 3
1 1 1 1
9 6 7 6
8 1 9 7
Sample Output 3
2
Scoring
Subtask ~1~ với ~30\%~ số điểm: ~r,s \le 20~
Subtask ~2~ với ~30\%~ số điểm: ~r,s \le 100~
Subtask ~3~ với ~40\%~ số điểm: Không còn ràng buộc gì thêm
Clarification
Trong ví dụ thứ hai, Matej có thể mua vùng đất từ ô ~(1,1)~ đến ô ~(2,1)~ hoặc vùng đất từ ô ~(2,2)~ đến ô ~(3,2)~. Tổng giá trị của vùng đất là ~1+1=2~ và tổng giá trị chênh lệch so với hai con số ma thuật là ~|2-3|+|2-4|=3~.
Comments
You need to sign in to write comments, reply and vote.
,
,
và
.
chứa
.
với
số điểm:
với
với
số điểm: Không còn ràng buộc gì thêm
Comments