Kosmik tədqiqatlar
Kosmik tədqiqatlar şöbəsinə kosmosdan müəyyən bir ərazidə n obyektin şəklini çəkmək tapşırığı verilib. Ərazi 50×50 kilometr ölçüsündə kvadrat şəklindədir. Əgər onu 1×1 kilometr ölçüsündə kvadratlara bölsək, şöbənin maraqlandığı obyektlər bəzi vahid kvadratların mərkəzlərində yerləşəcək.
Koordinat sistemini qərbdən şərqə doğru OX oxunu və cənubdan şimala doğru OY oxunu yönəldərək təqdim edək. Beləliklə, hər bir vahid kvadrata 1-dən 50-ə qədər koordinatlar uyğun gələcək, aşağıdakı şəkildə göstərildiyi kimi.
Kosmik çəkiliş üçün xüsusi yüksək dəqiqlikli fotoaparat istifadə olunur, bu fotoaparat kosmik peykə quraşdırılıb. Fotoaparat k×k kilometr ölçüsündə yer səthinin kvadrat sahələrinin şəkillərini çəkə bilər. Başlanğıcda aparat verilmiş ərazinin cənub-qərb küncünə yönəldilib, yəni şəkil çəkilsə, x və y koordinatları 1-dən k-ə qədər olan vahid kvadratlar görünəcək.
Xüsusi mühərriklər vasitəsilə peykin orbitini dəyişmək mümkündür, bu da çəkiliş sahəsinin dəyişməsinə səbəb olur. Bir gün ərzində peykin orbitini elə dəyişmək olar ki, çəkiliş sahəsi ya bir kilometr qərbə, ya bir kilometr şərqə, ya da bir kilometr şimala sürüşsün. Çəkiliş sahəsini cənuba doğru sürüşdürmək mümkün deyil. Peykin hərəkətləri arasında birbaşa şəkil çəkmək mümkündür, çəkiliş vaxtını nəzərə almamaq olar.
Şöbə rəhbərliyi maraqlanır: verilmiş ərazidəki bütün obyektlərin şəkillərini çəkmək üçün minimum neçə gün lazımdır.
Verilmiş obyektlərin yerləşməsi və şəkil ölçüsü k əsasında bütün obyektlərin şəkillərini çəkmək üçün minimum vaxtı müəyyən edən bir proqram yazmaq lazımdır.
Giriş verilənləri
Giriş faylının ilk sətiri iki tam ədəd ehtiva edir: n və k (1 ≤ n ≤ 1000, 1 ≤ k ≤ 5).
Növbəti n sətir hər biri iki tam ədəd ehtiva edir: x_i və y_i — verilmiş ərazidə obyektlərin koordinatları (1 ≤ x_i, y_i ≤ 50).
Çıxış verilənləri
Çıxış faylında bir tam ədəd olmalıdır: verilmiş ərazidəki bütün obyektlərin şəkillərini çəkmək üçün lazım olan minimum günlərin sayı.
Nümunələrə izah
Birinci nümunədə mümkün hərəkət ardıcıllığı belədir: şəkil çəkmək, 9 dəfə şərqə sürüşmək, şimala sürüşmək, şəkil çəkmək, 9 dəfə qərbə sürüşmək, şimala sürüşmək, şəkil çəkmək, 9 dəfə şərqə sürüşmək, şimala sürüşmək, şəkil çəkmək. Ümumilikdə 30 çəkiliş sahəsi hərəkəti lazımdır.
İkinci nümunədə obyektlər eyni yerdə yerləşir, lakin şəkil ölçüsü daha böyükdür, buna görə də belə hərəkət etmək olar: şəkil çəkmək, şimala sürüşmək, şəkil çəkmək, 8 dəfə şərqə sürüşmək, şəkil çəkmək, şimala sürüşmək, şəkil çəkmək. Ümumilikdə yalnız 10 çəkiliş sahəsi hərəkəti lazımdır.
Üçüncü nümunədə çəkiliş sahəsini hərəkət etdirmək lazım deyil, sadəcə şəkil çəkmək olar.
Dördüncü nümunə yuxarıda göstərilən şəkildəki nümunəyə uyğundur.