Nosaukums
Punktzemes zaldāti (zaldati)
Laika limits
1.00s
Atmiņas limits
256.0 MB

Definīcija

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.


Ievaddatu raksturojums

Ievaddatu 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.


Izvaddatu raksturojums

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


Piezīmes

Uzdevums izmantots Centrāleiropas valstu informātikas olimpiādē 1998.gadā.


Paraugdati

Stdin
3
1 0
2 4
3 2
Stdout
4

Stdin
5
1 2
2 2
1 3
3 -2
3 3
Stdout
8

Uzdevums tiek aizsargāts ar autortiesībām un tā kopēšana vai neatļauta izmantošana ir aizliegta.