Krımda işlər
Krım — nə qədər gözəl bir yerdir... Hər tərəfi dənizlə əhatə olunmuş, hər şəhərində dünyada bənzəri olmayan qeyri-adi bir şey var. Orada nə qədər kurort şəhəri var: Sevastopol, Yalta, Yevpatoriya, Aluşta, Sakı və daha bir çoxu. Ukraynada və onun hüdudlarından kənarda tanınan nə qədər məkanlar var: Xersones, Baxçasaray, Manqup-Qale, Eski-Kermen. Saymaqla bitməz. Amma Krımın şəhərlərinin belə gözəl və cəlbedici olması üçün onların təmizliyinə daim nəzarət etmək lazımdır və bu, Krım sakinlərinin çox gücünü alır.
Bu səbəbdən Krımın proqramçıları hər şəhərdə çox tez və keyfiyyətli təmizlik işləri aparacaq xüsusi bir robot-təmizləyici icad etdilər. Robot çox sürətli olduğu üçün bir şəhərdən digərinə demək olar ki, gözə çarpmadan keçərək bir çox şəhərlərin təmizliyinə nəzarət edə biləcək. Amma bir problem var: robot xüsusi yanacaqla işləyir və yalnız şəhərlərdə yanacaq doldura bilər, yolda isə yanacaq doldura bilməz. Bizə məlumdur ki, o, yanacaq doldurmadan neçə kilometr gedə bilər. Aydındır ki, bir robot bütün şəhərlərə xidmət edə bilməyəcək, çünki bəzi şəhərlərə çatmaq üçün robotun maksimum mümkün məsafəsini aşan məsafəni qət etmək lazım gələcək.
Tutaq ki, bütün yollar koordinat oxlarına paraleldir, buna görə də şəhərlər arasındakı məsafəni aşağıdakı kimi ölçəcəyik: r = |x_1 - x_2| + |y_1 - y_2|. Proqramçılar artıq müxtəlif yanacaq çənlərinin ölçüləri olan M model robot hazırlayıblar. Onların hər biri üçün yanacaq doldurmadan neçə kilometr gedə biləcəyi məlumdur. İndi hökumət maraqlanır: bütün şəhərlərə xidmət edə bilmək üçün müəyyən bir modeldən neçə robot lazım olacaq?
Giriş verilənləri
Birinci sətir təbii ədəd N (1 ≤ N ≤ 2000) - şəhərlərin sayını ehtiva edir. Növbəti N sətirin hər biri hər bir şəhərin koordinatlarını göstərən iki ədəd x_i, y_i ehtiva edir. Bütün koordinatların tam ədədlər olduğu və modulu 10^9-dan çox olmadığı təmin edilir. Sonra proqramçılar tərəfindən təqdim olunan robot modellərinin sayı M (1 ≤ M ≤ 5·10^5) gəlir. Növbəti M sətirin hər biri bir tam ədəd K (0 ≤ K ≤ 2·10^9) ehtiva edir ki, bu da robotun yanacaq doldurmadan gedə biləcəyi məsafəni göstərir. Robotun istənilən şəhər daxilində trolleybus xətləri ilə elektrik enerjisi ilə işlədiyini qəbul etmək olar, buna görə yanacaq yalnız şəhərlər arasında hərəkət üçün sərf olunur.
Çıxış verilənləri
Hər bir sorğu üçün bir ədəd çıxarın — bütün şəhərlərə xidmət edə biləcək həmin modeldən olan robotların minimum sayı.