Nhà máy đang thử nghiệm -robot trên một lưới ô vuông khổng lồ. Một số ô là điểm sạc (chứa ổ cắm điện). Robot lúc đầu đứng ở một ô. Sau khi vận hành, robot sẽ đi qua một số ô, ở mỗi ô một số nguyên dương phút, rồi sau đó sẽ di chuyển sang ô hàng xóm kề cạnh (thời gian di chuyển là không đáng kể). Hãy xác định giá trị lớn nhất có thể của khoảng cách bé nhất từ Robot đến một điểm sạc nào đó sau khi robot vận hành phút. Khoảng cách được sử dụng là khoảng cách Manhattan.
Khoảng cách Manhattan giữa hai ô có tọa độ và là
Hình minh họa
Trong ví dụ trên điểm sạc là các ô màu đen, robot ban đầu ở ô có vòng tròn trắng. Sau phút, robot có thể đến ô và lúc này khoảng cách gần nhất đến một điểm sạc là . Và đó là giá trị lớn nhất.
Dữ liệu vào:
Dòng đầu ghi số điểm sạc và số phút thử nghiệm .
Sau đó là dòng, mỗi dòng ghi số nguyên là tọa độ một điểm sạc .
Dòng cuối ghi tọa độ lúc ban đầu của robot. Các tọa độ thỏa mãn . Toàn bộ điểm đôi một phân biệt.
Dữ liệu ra:
In ra giá trị lớn nhất của khoảng cách bé nhất từ robot đến một điểm sạc.
