Fişierul intrare/ieşire:	greutati.in, greutati.out	Sursă	Algoritmiada 2018 Runda PreONI
Autor	Mihai Calancea	Adăugată de	Radu Muntean •heracle
Timp execuţie pe test	0.5 sec	Limită de memorie	262144 kbytes
Scorul tău	N/A	Dificultate	N/A

Vezi solutiile trimise | Statistici

Greutati

Se dau N tipuri de numere. Pentru fiercare tip i numerotat de la 0 la N - 1 se stie ca sunt (FR_i). Numerele de tipul i sunt egale cu 2ⁱ. Sa se partitioneze numerele 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).

Date de intrare

Fişierul de intrare greutati.in se vor afla pe prima linie 2 numere intregi N si P, unde N reprezinta numarul de puteri de 2 pentru care frecventa este diferita de 0, iar P reprezinta puterea maxima la care poate aparea 2. Pe urmatoarele N linii se vor afla cate 2 numere intregi PW_i si FR_i reprezentand o putere si o frecventa corespunzatoare acelei puteri.

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

Restricţii

• 1 ≤ N ≤ 100.000
• 1 ≤ P ≤ 1.000.000.000
• 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
• Pentru 25 de puncte: P <= 50, suma frecventelor <= 2000
• Pentru 35 de puncte: P <= 2000, suma frecventelor <= 2000
• Pentru 50 de puncte: P <= 100.000, suma frecventelor <= 100.000
• Pentru 70 de puncte: P <= 100.000 si suma frecventelor <= 1.000.000.000

Exemplu

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

Cum se trimit solutii?