ვირუსები

დროის ლიმიტი: 1 წმ

მეხსიერების ლიმიტი: 64 მეგაბაიტი

შემავალი მონაცემები: stdin

გამომავალი მონაცემები: stdout


n×n (n≤500) ზომის უჯრედოვან არეზე მოთავსებულია m (1≤m≤10) ვირუსი. ყოველ სვლაზე ვირუსი ასნებოვნებს მის 4 მეზობელ უჯრედს (მარცხნივ, მარჯვნივ, ზემოთ, ქვემოთ). დაწერეთ პროგრამა, რომელიც გაარკვევს სვლების იმ უმცირეს რაოდენობას, რომელიც საჭიროა მოცემული არის მთლიანად დასნებოვნებისთვის

შემავალი მონაცემები: პირველ სტრიქონში მოცემულია ორი მთელი რიცხვი – n და m. მეორიდან m+1 სტრიქონამდე მოცემულია ორი მთელი რიცხვი – ვირუსის კოორდინატები.

გამომავალი მონაცემები: ერთადერთ სტრიქონში უნდა გამოიტანოთ ერთი მთელი რიცხვი – სვლების უმცირესი რაოდენობა, რომლითაც შეიძლება არე მთლიანად დაიფაროს.

 




მაგალითები

შესატანი მონაცემები
5 1 2 3 დაკოპირება
გამოსატანი მონაცემები
5 დაკოპირება