Fișierul intrare/ieșire	antitir.in, antitir.out	Sursă	Baraj Shumen 2012, Juniori
Autor	Cristian Frâncu	Adăugată de	Cristian Frâncu • francu
Timp de execuție pe test	0.8 sec	Limită de memorie	16384 KB
Scorul tău	N/A	Dificultate	4

Poți vedea testele pentru această problemă accesând atașamentele .

Vezi soluțiile trimise | Statistici

Antitir

Notă: este necesară o implementare eficientă.

Se dau coordonatele a n săgeți înfipte într-un panou. Coordonatele săgeților sînt întregi. Pot exista mai multe săgeți în aceelași punct din panou. Dispunem de o țintă care poate fi deplasată pe panou astfel încît centrul ei să fie aliniat la coordonate întregi. Pentru o săgeată aflată la distanță x pe orizontală și y pe verticală de centrul țintei ea acordă x + y puncte.

Cerință

Să se găsească o poziționare a țintei pe panou astfel încît suma punctajului săgeților să fie minimă.

Date de intrare

Prima linie a fișierului antitir.in conține numărul de săgeți, n. Următoarele n linii conțin cîte o pereche de numere (x _i, y _i), coordonatele unei săgeți.

Date de ieșire

Fișierul antitir.out va conține un singur număr, punctajul minim care se poate obține.

Restricții

• 1 ≤ n ≤ 1000000
• -1000000000 ≤ x _i, y _i ≤ 1000000000 (x _i și y _i fiind coordonatele săgeților)
• În 60% din teste 0 ≤ x _i, y _i ≤ 1000000
• În 30% din teste n ≤ 1000 și 0 ≤ x _i, y _i ≤ 1000

Exemple