Dubluveu a fost ales de curand primar in "Popricani":http://ro.wikipedia.org/wiki/Comuna_Popricani%2C_Ia%C5%9Fi. Ca sa poate obtine "fondurile structurale":http://www.fonduri-structurale.ro pentru dezvoltarea comunei, proaspatul ales trebuie sa-si desemenze cat mai repede consilierii locali. Pentru ca in campania electorala, le-a promis popricanenilor ca nu va face discrimanari (ca si primarul precedent), va trebui sa respecte urmatoarele norme:

* Cosiliul Local trebuie sa aiba $N$ angajati (cate un singur angajat din fiecare casa, din cele $N$ ale comunei)

* Cosiliul Local trebuie sa aiba $N$ angajati

* va trebui sa angajeze atat barbati, cat si femei
* valoarea totala a discriminarii sa fie minima.

Putem considera comuna ca un plan cartezian, unde casele sunt reprezentate de puncte, iar ulitele sunt reprezentate de dreptele paralele cu axele de coordonate, pe care se alfa cel putin o casa (vezi figura).  Discriminarea pe o astfel de ulita este egala cu diferenta (in modul) dintre numarul de barbati si numarul de femei alesi in Consiliul Local. Discriminarea totala este suma discriminarilor de pe fiecare ulita.

Putem considera comuna ca un plan cartezian, unde casele sunt reprezentate de puncte, iar ulitele sunt reprezentate de dreptele paralele cu axele de coordonate, pe care se alfa cel putin o casa (vezi figura).  Discriminarea pe o astfel de ulita este egala cu diferenta (in modul) dintre numarul de barbati si numarul de femei alesi in Consiliul Local.

!problema/primar?grid.jpg!

h2. Restrictii

* $1$ ≤ $N$ ≤ $131 072$
* coordonatele caselor sunt numere intregi ale caror coordonate nu depasesc, in modul, $2 000 000 000$
* daca o ulita are doar o singura casa atunci, +indiferent de alegerea facuta+, discriminarea pe acea ulita va fi $0$.
* intr-o casa locuiesc cel putin un barbat si cel putin o femeie
* nu exista doua case la aceeasi coordonata
* veti primi $40%$ din punctaj pentru determinarea corecta a discriminarii minime si $100%$ daca raspundeti corect la intreaga cerinta

* $1 ≤ N ≤ 200 000$
* $coordonatele caselor sunt numere intregi ale caror coordonate nu depasesc, in modul, 2 000 000 000$
* daca o ulita are doar o singura casa atunci, +indiferent de alegerea facuta+, discriminarea pe acea ulita va fi 0.
* $intr-o casa locuiesc cel putin un barbat si cel putin o femeie$
* $vei primi 2 puncte pentru determinarea corecta a discriminarii minime si alte 3 puncte daca raspunzi corect la intreaga cerinta$

h2. Exemplu

h3. Explicatie

din casele 2, 3 si, respectiv, 5 vei alege cate un barbat, iar din casele 1 si 4 vei alege cate o femeie.

din casele 2, 3 si, respectiv, 5 casa vei alege cate un barbat, iar din casele 1 si 4 vei alege cate o femeie.

!problema/primar?ex.jpg!

== include(page="template/taskfooter" task_id="primar") ==

2639