Let's begin with a somewhat easier task: given an integer ~d~, we need to find out whether the sheriff can keep the BEARs at least distance ~d~ from the warehouse. In other words, determine if the sheriff can block streets in such a way that the BEARs cannot enter any intersection strictly bounded by a square with vertices at ~(\pm d, \pm d)~. Let ~K~ be the set of intersections within this square (excluding intersections on edges and vertices).

Let ~A~ be the set of intersections such that if the BEARs start in an intersection in ~A~, they will be able to reach an intersection in ~K~ no matter what the sheriff will do. We can express ~A~ as the minimal set of intersections such that any intersection ~S~ is in set ~A~ if at least one of the following holds:

1. ~S~ is in ~K~;
2. there is a main street segment from ~S~ leading to an intersection in ~A~;
3. at least two of the neighbouring intersections are in ~A~.

Note that because of 3, ~A~ will always be a rectangle.

We can construct the set ~A~ iteratively. Let's begin with ~A = K~. Then for every main street that has at least one intersection in ~A~, we extend ~A~ so that it would include all intersections in that main street. We do this until there are no main streets to add.

Now, if the intersection ~(a, b)~ is in ~A~, the BEARs will reach an intersection in ~K~.

We can now use binary search to find the maximum value of ~d~ for which the BEARs won't be able to reach ~K~.

We construct the set ~A~ in ~\mathcal O(N^2)~, thus we solve the task in ~\mathcal O(N^2 \log \max(|A|, |B|))~.