Fișierul intrare/ieșire	bibelouri.in, bibelouri.out	Sursă	CodeChef
Autor	autor necunoscut	Adăugată de	Cătălin Frâncu • Catalin.Francu
Timp de execuție pe test	0.1 sec	Limită de memorie	524288 KB
Scorul tău	N/A	Dificultate	1.5

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

Vezi soluțiile trimise | Statistici

Bibelouri

Notă: Această problemă este inspirată după Mike and Stamps

Ești proprietarul unui magazin de bibelouri. Ai de vînzare n bibelouri unicat, numerotate de la 1 la n.

În magazin intră m clienți și fiecare cere să cumpere o submulțime a celor n bibelouri. Toate cererile sînt „totul sau nimic”: nu îi poți satisface doar parțial cererea niciunui client, dar îl poți refuza complet. Desigur, poți vinde un bibelou unui singur client.

Care este numărul maxim de bibelouri pe care îl poți vinde?

Date de intrare

Fișierul de intrare bibelouri.in conține pe prima linie numerele m și n. Pe următoarele m linii se află cîte n caractere 0 sau 1, unde al j$-lea caracter de pe a $i$-a linie este $1 dacă clientul i vrea să cumpere bibeloul j sau 0 în caz contrar.

Date de ieșire

În fișierul de ieșire bibelouri.out afișați numărul maxim de bibelouri vîndute.

Restricții

• 1 ≤ m ≤ 25
• 1 ≤ n ≤ 50.000
• Există 20 de teste, fiecare valorînd 5 puncte.
• Testele au m = 6, 7, 8, ... , 24, 25, iar n crește progresiv pînă la 50.000.
• Testele nu sînt grupate.

Exemplu

Explicație

Vindem bibelourile 1 și 3 clientului 2, iar bibelourile 4 și 5 clientului 4.