magnify

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

Pradiniai duomenys Rezultatai Paaiškinimas
6
-8 12
0 5
7 -3
10 -7
-2 7
1 4
-34
Į reiškinį statome iš eilės 1-ą, 2-ą, 3-ą, 5-ą, 4-ą, 6-ą korteles:
(-8) – 5 + (-3) – 7 + (-7) – 4 = -34;
10
70 70
62 73
81 65
59 77
99 40
35 88
80 57
76 67
85 57
53 96
-155
Į reiškinį statome iš eilės 2-ą, 1-ą, 4-ą, 3-ą, 5-ą, 8-ą, 6-ą, 9-ą, 7-ą, 10-ą korteles:
62 – 70 + 59 – 81 + 40 – 76 + 35 – 85 + 57 – 96 = -155
© Bronė Narkevičienė