Poveste şi cerinţă...

Se dau N tipuri de numere, din fiercare tip i de la 0 la N - 1 se stie ca sunt (FR[ i ]). Numerele de tipul i sunt egale cu 2 ^ i. Sa se partitioneze numerele in 2 multiseturi astfel incat sumele celor 2 sa fie cat mai apropiate. Aflati aceasta diferenta (in modul) minima modulo 1000004249 (e prim).
N <= 10 ^ 6
FR[ i ] <= 10 ^ 9
 
primele 10p: N, SumaFR <= 30
urmatoarele 10p: N <= 30
inca 40p: SumaFR <= 10 ^ 6
ultimele 40p: fara alte restrictii
 

h2. Date de intrare
Fişierul de intrare $greutati.in$ ...