Punktzemes zaldāti

ID: zaldati
Grūtība: 4/5
Laika limits: 1

Uzdevums

N Punktzemes zaldāti ir izvietoti pa visu valsti.

Vietu Punktzemē nosaka ar divu veselu skaitļu koordinātu pāra (x,y) palīdzību. Katrs zaldāts var pārvietoties - vienā solī viņš var paiet vienu vienību pa labi, pa kreisi, uz augšu vai uz leju (tādējādi šī zaldāta x vai y koordināta izmainīsies par 1).

Zaldātu mērķis ir nostāties horizontālā ierindā vienam blakus otram (tātad beigās zaldātu koordinātas būtu (x,y), (x+1,y),...,(x+N-1,y) ). Skaitļu x un y, kā arī zaldātu secība šajā ierindā ir patvaļīga.

Uzdevums ir atrast mazāko gājienu skaitu, kas ļautu zaldātiem nostāties aprakstītajā ierindā.

Nevienā brīdī nevienā punktā nedrīkst atrasties vairāk par vienu zaldātu.

 

Ievaddati

Teksta faila zaldati.in pirmā rinda satur naturāla skaitļa N(1<=N<=10000) vērtību.
Nākošajās N faila rindas apraksta zaldātu sākuma atrašanās vietas, pa vienam zaldātam katrā rindā. Katram i (1<=i<=N) faila i+1-ajā rindā ir dotas i-tā zaldāta sākuma atrašanās vietas koordinātas x[i] un y[i], kas atdalītas ar tukšumsimbolu. Zināms, ka -10000<=x[i],y[i]<=10000.

 

Izvaddati

Teksta faila zaldati.out vienīgajā rindā jāizvada viens vesels skaitlis - mazākais soļu skaits, kas zaldātiem ļautu nostāties iepriekšaprakstītajā ierindā.

 

Piemērs

zaldati.inzaldati.out
3
1 0
2 4
3 2
4
zaldati.inzaldati.out
5
1 2
2 2
1 3
3 -2
3 3
8

 

Atsauces

Uzdevums izmantots Centrāleiropas valstu informātikas olimpiādē 1998.gadā.
© 2001-2002 olimps! http://www.lio.lv/olimps/