Kortelės

Pradinių duomenų failas:

korteles.in  

Rezultatų failas:

korteles.out  

Laiko apribojimas:

1 s.  

Atminties apribojimas:

16 Mb.  

Užduotis

Adomui patinka skaičiai. Kartą, radęs stalčiuje krūvą nereikalingų kortelių, jis ant abiejų jų pusių užrašė įvairius skaičius (po vieną skaičių ant kiekvienos kortelės pusės) ir susigalvojo sau įdomų uždavinį: kokį mažiausią skaičių galima gauti įstatant visas turimas korteles (atverstas kuria nors puse) į tokį reiškinį:

[] - [] + [] - [] + [] - [] + ... - []

Šiek tiek pagalvojęs Adomas rado sprendimą šiam uždaviniui. Ar galite ir Jūs? Parašykite programą, sprendžiančią aprašytąjį uždavinį.

Pradiniai duomenys

Pirmoje pradinių duomenų eilutėje įrašytas kortelių skaičius N (2 <= N <= 100000, N – lyginis skaičius). Tolesnėse N eilučių įrašyta po du sveikuosius skaičius \(a_{i}\) ir \(b_{i}\) – tai ant i-tosios kortelės skirtingų pusių užrašyti skaičiai (-2000 <= \(a_{i}\), \(b_{i}\) <= 2000; i = 1…N).

Rezultatai

Pirmoje rezultatų eilutėje turi būti įrašytas mažiausias skaičius, kurį galima gauti įstačius korteles į reiškinį.

Pavyzdžiai

6
-8 12
0 5
7 -3
10 -7
-2 7
1 4

-34

10
70 70
62 73
81 65
59 77
99 40
35 88
80 57
76 67
85 57
53 96

-155