Роботи в Криму#4550
Крим — прекрасне місце, оточене з усіх боків морем. Кожне місто тут має щось унікальне, таке, чого не знайти більше ніде у світі. Багато курортних міст: Севастополь, Ялта, Євпаторія, Алушта, Саки та багато інших. Є також пам'ятки, відомі не лише в Україні, а й за її межами: Херсонес, Бахчисарай, Мангуп-Кале, Ескі-Кермен. Цей перелік можна продовжувати дуже довго. Але для того, щоб кримські міста залишалися такими красивими та привабливими, їхню чистоту потрібно постійно підтримувати, що вимагає чималих зусиль від жителів.
Саме тому кримські програмісти винайшли спеціального робота-прибирача, який може ефективно прибирати кожне місто. Оскільки робот дуже швидкий, він може встигати підтримувати чистоту в багатьох містах, майже непомітно пересуваючись з одного в інше. Однак є одна проблема: робот працює на спеціальному паливі, і заправлятися він може лише у містах, а не на дорозі між ними. Відомо, скільки кілометрів робот може проїхати до наступної заправки. Очевидно, що один робот не може обслуговувати всі міста, адже до деяких потрібно їхати на відстань, що перевищує його максимальний можливий пробіг без заправки.
Вважатимемо, що всі дороги паралельні до координатних осей, а відстань між містами вимірюється як:
Програмісти вже розробили моделей роботів з різною місткістю паливного бака. Для кожної моделі відома максимальна відстань, яку вона може проїхати без заправки. Тепер стоїть питання: скільки роботів даної моделі потрібно, щоб усі міста були обслуговувані?
У першому рядку міститься натуральне число (1 \leq N \leq 2000) — кількість міст. У кожному з наступних рядків знаходяться два цілих числа x_i, y_i — координати кожного міста. Усі координати — цілі числа, їх абсолютна величина не перевищує 10^9.
Наступний рядок містить число (1 \leq M \leq 5 \cdot 10^5) — кількість моделей роботів. У кожному з наступних рядків знаходиться одне ціле число (0 \leq K \leq 2 \cdot 10^9) — відстань, яку ця модель робота може подолати без заправки.
Можна вважати, що всередині міста роботи працюють на електриці (від тролейбусних дротів :)), тому паливо використовується лише для пересування між містами.
Для кожної моделі робота виведіть одне число — мінімальну кількість роботів цієї моделі, необхідну, щоб обслуговувати всі міста.
Приклад
3
4 2
4 5
7 5
2
2
42
1Приклад 1
У першому запиті робот не може дістатися до жодного іншого міста з кожного міста, тому потрібно роботи. У другому запиті робот може дістатися до кожного міста з будь-якого іншого, тому достатньо робота.