Rezolvare PBinfo #3832

Cerința

Dându-se N puncte laticiale, care este distanța Manhattan de buget minimă dintre două puncte de coordonate a b respectiv x y cu proprietatea că a-y >= x-b?

Date de intrare

Fișierul de intrare mman.in conține pe prima linie numărul N, iar pe următoarele n linii se află câte două numere, pe linia i se află coordonatele x respectiv y ale punctului i.

Date de ieșire

Fișierul de ieșire mman.out va conține pe prima linie numărul M reprezentând valoarea cerută.

Restricții și precizări

• 2 ≤ n ≤ 100.000
• coordonatele tuturor punctelor aparțin intervalului [-1.000.000.000, 1.000.000.000].
• Distanța Manhattan de buget dintre punctul cu coordonate a b si punctul de coordonate x y este a-x+b-y.

Exemplu:

mman.in

3
1 1
2 3
-1 -1

mman.out

3

Explicație

Distanța minimă dintre două puncte se obține din punctele cu coordonate 1 1 și 2 3.