ტალახიანი გუბეები

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

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

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

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

წყარო: USACO, 2007/08, DEC, SILVER


ფერმერი ჯონი მიდის ბესის მოსანახულებლად. რადგან წინა საღამოს იყო ძლიერი წვიმა, მინდვრები არის ტალახიანი. ჯონი სვლას იწყებს პოზიციიდან (0, 0) და უნდა მივიდეს ბესიმდე -(X,Y)პოზიციამდე. (-500 <= X <= 500; -500 <= Y <= 500). მას შეუძლია დაინახოს ყველა N (1 <= N<= 10,000) ტალახიანი გუბე, რომელთა განლაგების კოორდინატები ველზე არის(A_i, B_i). (-500 <= A_i<= 500; -500 <= B_i <= 500). ყოველი გუბე ფარავს მხოლოდ იმ პოზიციას, სადაც ის მდებარეობს.

აცვია რა ახალი ნაყიდი ფეხსაცმელები, ჯონს არ უნდა დაისვაროს ისინი გუბეში, მაგრამ მას ამავე დროს უნდა მივიდეს ბესიმდე რაც შეიძლება სწრაფად. მას უკვე აგვიანდება, რადგან დრო დაკარგა გუბეების გადათვლაზე. თუ ჯონს შეუძლია იმოძრაოს კოორდინანტთა ღერძების პარალელურად, რა მინიმალური მანძილი უნდა გაიაროს ჯონმა რომ მივიდეს ბესისთან და ამასთან ფეხსაცმელი არ დაისვაროს? გარანტირებულია რომ ასეთი გზა ყოველთვის არსებობს.

შეტანის ფორმატი:

* ხაზი 1: სამი ჰარით გაყოფილი მთელი: X, Y და N.

* ხაზები 2..N+1: ხაზი i+1 შეიცავს ორი ჰარით გაყოფილი მთელს: A_i და B_i

 

გამოტანის ფორმატი:

* ხაზი 1: მინმალური გზა, რომელიც ფერმერმა ჯონმა უნდა გაიაროს ბესიმდე მისასვლელად.

 

 




მაგალითები

შესატანი მონაცემები
1 2 7 0 2 -1 3 3 1 1 1 4 2 -1 1 2 2 დაკოპირება
გამოსატანი მონაცემები
11 დაკოპირება

შენიშვნა

შეტანის დეტალები:

ბესი არის (1, 2) პოზიციაში. ფერმერი ჯონი ხედავს 7 გუბეს განლაგებულს (0,2); (-1, 3); (3, 1); (1, 1); (4, 2); (-1, 1) და (2, 2) პოზიციებში. 

 გამოტანის დეტალები:

ერთ-ერთი საუკეთესო გზა ჯონისათვის არის (0, 0); (-1, 0); (-2, 0); (-2, 1); (-2, 2); (-2, 3); (-2, 4); (-1, 4); (0, 4); (0, 3); (1, 3) და (1,2) 

და მიაღწევს ბესის. 

 

 

   4 * * * * . . . . 

   3 * M . * . . . . 

Y  2 * . M B M . M . 

   1 * M . M . M . . 

   0 * * * . . . . . 

  -1 . . . . . . . . 

    -2-1 0 1 2 3 4 5 

           X