== include(page="template/taskheader" task_id="greutati") ==

Se dau $N$ tipuri de numere. Consideram un vector de elemente cu proprietatea ca pentru fiercare tip $i$ numerotat de la $0$ la $N - 1$ acesta apare de (FR{~i~}) ori. Numerele de tipul $i$ sunt egale cu $2^i^$. Sa se partitioneze elementele vectorului in $2$ multiseturi astfel incat sumele celor doua sa fie cat mai apropiate (diferenta in modul sa fie minima). Aflati aceasta diferenta minima *$modulo 1.000.000.007*$ (acest numar e prim).

Se dau $N$ tipuri de numere. Consideram un vector de elemente cu proprietatea ca pentru fiercare tip $i$ numerotat de la $0$ la $N - 1$ acesta apare de (FR{~i~}) ori. Numerele de tipul $i$ sunt egale cu $2^PW{~i~}^$. Sa se partitioneze elementele vectorului in $2$ multiseturi astfel incat sumele celor doua sa fie cat mai apropiate (diferenta in modul sa fie minima). Aflati aceasta diferenta minima *$modulo 1.000.000.007*$.

h2. Date de intrare

h2. Date de ieşire

Fişierul de ieşire $greutati.out$ va contine un singur numar natural reprezentand diferenta minima pen care o puteti obtine *$modulo 1.000.000.007$*

Fişierul de ieşire $greutati.out$ va contine un singur numar natural reprezentand diferenta minima pe care o puteti obtine *$modulo 1.000.000.007$*.

h2. Restricţii
* $1 ≤ N ≤ 100.000$
* $1 ≤ P ≤ 1.000.000.000$

* $0 ≤ PW{~i~} < P$

* $0 ≤ PW{~i~} ≤ P$

* $1 ≤ FR{~i~} ≤ 1.000.000.000$
* nu vor exista perechi $i$ si $j$ in input astfel incat $PW{~i~} = PW{~j~}$
* Pentru $15$ puncte: $P <= 20$, suma frecventelor $<= 20$

|5
|

h3. Explicaţie
 
sirul frecventelor este 0 0 4 3 1 2 4 3 0 0, respectiv 0 0 4 3 1 2 4 3 0 3

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