Popeala

The Romanian word popeală comes from the historical novella "Alexandru Lăpușneanul". The word came back into use in the Romanian programming contest scene, where it describes any situation in which the scientific committee makes life harder for the contestants in an unorthodox and usually involuntary way: very strict time limits, invalid test data, wrong statements, stolen keyboards. This task is about one of those situations.

A contest has $N$ contestants. It has a single task, and that task has $T$ test cases. The committee wants to group these test cases into subtasks.

Subtasks work like this. Each test case belongs to exactly one subtask. A subtask may contain any number of test cases, but it cannot be empty. If a contestant fails any test case of a subtask, that contestant scores $0$ on that subtask. Otherwise the contestant scores the sum of the point values of all test cases in that subtask.

The committee does the grouping after the contest is over. It already knows which test cases each contestant solved, so it will group the test cases so that the total number of points scored in the contest is as small as possible.

You are given an array $\mathrm{Points}$ of size $T$, where $\mathrm{Points}[i]$ is the point value of the $i$-th test case. You are also given a matrix $\mathrm{Results}$ of size $N \times T$, where $\mathrm{Results}[i][j]$ is $1$ if the $i$-th contestant solved the $j$-th test case correctly and $0$ otherwise. The committee has already decided that every subtask holds consecutive test cases. In other words, if test cases $X$ and $Y$ end up in the same subtask, then every test case $Z$ with $X \le Z \le Y$ belongs to that subtask too.

For each $K$ with $1 \le K \le S$, find the minimum total number of points that can be scored in the contest when the test cases are grouped into exactly $K$ subtasks.

The first line contains three space-separated integers $N$, $T$, $S$.

The second line contains $T$ space-separated integers. The $i$-th of them is $\mathrm{Points}[i]$.

Each of the next $N$ lines contains a string of length $T$ made of the characters $0$ and $1$. The $j$-th character of the $i$-th such line is $\mathrm{Results}[i][j]$.

• $1 \le T \le 20000$
• $1 \le N \le 50$
• $1 \le S \le \min(50, T)$
• $1 \le \mathrm{Points}[i] \le 10000$ ($1 \le i \le T$)
• $(\mathrm{Points}[1] + \mathrm{Points}[2] + \dots + \mathrm{Points}[T]) \times N \le 2 \times 10^9$

Print $S$ lines. The $i$-th line contains one integer: the minimum total number of points that can be scored in the contest when the test cases are grouped into exactly $i$ subtasks.

In the first example there are $2$ contestants, $3$ test cases and $S = 3$, so the minimum has to be computed for $1$, $2$ and $3$ subtasks. The point values are $4$, $3$, $5$.

With a single subtask all three test cases fall into it. Neither contestant solved every test case, so the total is $0$.

With two subtasks there are two ways to group the test cases. One gives a total of $12$ points and the other gives $8$, so the smaller one, $8$, is chosen.

With three subtasks there is only one grouping, and it gives a total of $16$ points.