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

_Cuvântul românesc “popeală” îşi are originile în nuvela istorică românească "Alexandru Lăpuşneanu" unde Prinţul Moldovei foloseşte o serie de termeni pentru a descrie o viitoare răzbunare a sa asupra uzurpatorilor. Termenul a fost recent adoptat, oarecum surprinzător, pe scena concursurilor româneşti de programare. El este folosit pentru a descrie situaţiile când comisia face viaţa grea concurenţilor într-un mod neortodox şi (de regulă) involuntar: limite de timp foarte stricte, teste eronate, probleme greşite, tastaturi furate şi alte mecanisme. Această problemă se referă la o “popeală”._

_Cuvântul românesc “popeală” îşi are originile în nuvela istorică românească "Alexandru Lăpuşneanul" unde Prinţul Moldovei foloseşte o serie de termeni pentru a descrie o viitoare răzbunare a sa asupra uzurpatorilor. Termenul a fost recent adoptat, oarecum surprinzător, pe scena concursurilor româneşti de programare. El este folosit pentru a descrie situaţiile când comisia face viaţa grea concurenţilor într-un mod neortodox şi (de regulă) involuntar: limite de timp foarte stricte, teste eronate, probleme greşite, tastaturi furate şi alte mecanisme. Această problemă se referă la o “popeală”._

Considerăm un concurs de programare cu $N$ participanţi. Concursul are doar o problemă cu $T$ teste. Comisia ştiinţifică doreşte să grupeze testele în cel mult $S$ subprobleme. Cum funcţionează subproblemele: Fiecare test aparţine exact unei subprobleme. O subproblemă poate conţine un număr oarecare de teste dar cel puţin unul. Dacă un participant ratează cel puţin un test al unei subprobleme, punctajul său la această subproblemă va fi $0$. În caz contrar, scorul pentru această subproblemă va fi egal cu suma valorilor punctajelor tuturor testelor subproblemei. Aceasta este o practică obişnuită a concursurilor de programare, dar acum comisia doreşte să facă acest lucru după ce concursul se termină. Comisia ştie care sunt testele rezolvate corect de fiecare participant şi doreşte să grupeze testele fiecărei subprobleme astfel încât să minimizeze numărul total de puncte obţinut în concurs.
Concret, ţi se dă un şir de întregi $Points[]$ de dimensiune $T$. $Points[i]$ va conţine punctajul celui de-al $i$-lea test. Primeşti, de asemenea, un tablou bidimensional $Results[][]$ de dimensiune $N$ * $T$. $Results[i][j]$ va fi egal cu $1$ dacă al $i$-lea concurent a rezolvat corect cel de-al $j$-lea test. În caz contrar acesta va fi $0$. Comisia a decis deja că toate subproblemele vor conţine teste consecutive. Cu alte cuvinte, dacă testele $X$ şi $Y$ sunt conţinute de aceeaşi subproblemă, atunci orice test $Z$ cu $X ≤ Z ≤ Y$, se va afla în aceeaşi subproblemă. Tu trebuie să ajuţi comisia. Aceştia doresc să afle, pentru fiecare valoare $1 ≤ K ≤ S$, care este numărul total de puncte minim posibil ce se poate obţine în concurs dacă testele se vor grupa în exact $K$ subprobleme.