В недалеком будущем, для поступления в университет межгалатических отношений на факультет космического десанта потребуется сдавать экзамен по прохождению экстремальной трассы испытаний. На одном из этапов трассы нужно уничтожить все мишени при помощи оружия BFG9000. Можно считать, что мишени расположены в двухмерной плоскости. Оружие BFG9000 за один выстрел уничтожает все мишени, которые попали в квадрат размером s × s (чем мощнее BFG9000, тем больше квадрат), но только если в квадрате находится как минимум три мишени (BFG9000 не разменивается по мелочам) и стороны квадрата параллельны осям координат (выстрел должен быть ровным). Чтобы не возиться с повторным размещением мишеней, они сконструированы таким образом, что после уничтожения сразу воспроизводятся (т. е. они снова будут учитываться при попадании), при этом такие мишени уже будут считаться уничтоженными. Фактически, нужно стрелять по мишеням и попасть в каждую как минимум один раз и тогда этап будет считаться пройденным.

Юра уже давно занимается изучением всей полосы, и на момент поступления ему известно, в каких координатах будут располагаться мишени при стрельбе. Конечно, он мог взять самую мощную BFG9000 которая есть в его распоряжении, но чем мощнее оружие, тем оно тяжелее и тем менее комфортно с ним бегать. Поэтому Юра задался целью определить минимальную мощность BFG9000, которую он может взять с собой, чтобы он смог пройти этап стрельбы. Помогите Юре.