Description

You hosted a contest with $n$ participants. There is only one problem, and it has $m$ test points, numbered from $1$ to $m$. Each test point has a score $a_i$.

Now all contestants have submitted their programs and all submissions have been judged. You know which test points each person can pass.

You now need to arrange a bundled testing method by partitioning the test points into several consecutive intervals, where each interval contains at least one test point. For each interval, if there is at least one wrong test point, then no score is obtained for that interval; if all test points in the interval are correct, then the score of the interval is the sum of the scores of all test points in it.

Your goal is to minimize the sum of all participants' scores. For $1\le i\le S$, output the minimum possible total score of all participants when all test points are partitioned into $i$ groups.

Input Format

The first line contains three integers $n,m,S$.

The next line contains $m$ integers, representing $a_i$.

The next $n$ lines each contain a binary string of length $m$ consisting of $0$ and $1$, where it indicates whether person $i$ passes test point $j$.

Output Format

Output $S$ lines. Each line contains one integer, representing the minimum possible total score of all participants when the test points are partitioned into $i$ bundled groups.

2 3 3
4 3 5
101
110

0
8
16

Hint

For $100\%$ of the testdata, $1\le n\le 50$, $1\le m\le 2\times 10^4$, $S\le \min(50,m)$, $1\le a_i \le 10^4$, $\Sigma a_i\times n\le 2\times10^9$.

Translated by ChatGPT 5