eolymp
Competitions

III Open Distance Programming Olympiad name V.L.Didkovsky 2013-2014

Роботы в Крыму

prb4550

Крым – насколько это красивое место... Со всех сторон его окружает море, в каждом городе есть что-то необычное, что-то такое, чего нет во всем мире. Сколько там курортных городов: Севастополь, Ялта, Евпатория, Алушта, Саки и множество других. Сколько мест, известных не только в Украине, но и за ее пределами: Херсонес, Бахчисарай, Мангуп-Кале, Эски-Кермен. Перечислять можно очень долго. Но чтобы города Крыма были столь красивыми и привлекательными необходимо постоянно следить за их чистотой, а на это уходит очень много сил крымских жителей.

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

Предположим, что все дороги параллельны осям координат, поэтому расстояние между городами будем измерять следующим образом: r = |x1–x2|+|y1–y2|. Программисты уже написали M моделей роботов с различными размерами бензобака. Для каждого из них известно, сколько километров без заправки он может пройти. Теперь правительство заинтересовалось: сколько же понадобится роботов некоторой модели, чтобы они могли обслуживать все города?

Входные данные

Первая строка содержит натуральное число N (1N2000) - количество городов. Каждая из последующих N строк содержит по два числа xi, yi – координаты каждого города. Гарантируется, что все координаты целые числа и по модулю не превышают 109. Далее следует число M (1M5·105) – количество моделей роботов, которые предоставили программисты. В каждой из следующей M строк содержится одно целое число K (0K2·109), показывающее расстояние, которое может пройти данная модель робота без заправки. Можно считать, что внутри любого города робот работает на электричестве (от троллейбусных проводов :) ), поэтому горючее тратится только на передвижение между городами.

Выходные данные

Для каждого из запросов выведите одно число – минимальное количество роботов данной модели, которые смогут обслуживать все города.

Time limit 3 seconds
Memory limit 256 MiB
Input example #1
3
1 1
2 2
3 4
3
6
1
2
Output example #1
1
3
2
Author Александр Бурков
Source III Открытая Дистанционная Олимпиада 2013-2014 им. В.Л.Дидковского