Bundled Testing Partitioning

You are organizing a contest where there are $n$ contestants and only one problem. The problem has $m$ test cases, numbered from $1$ to $m$, and each test case $i$ is assigned a score $a_i$. After all contestants have submitted their solutions, you know for each contestant which test cases they passed (each test case is either passed or failed by a contestant).

You are allowed to bundle the test cases into several groups. In each group, the test cases must form a contiguous segment of the original ordering (each group must contain at least one test case). A contestant will only earn the score of a group if they pass every test case in that group; if they fail at least one test case in the group, they get $0$ points for that group. In other words, if a group covers the interval $[l, r]$, then a contestant obtains the group’s score (which is $\sum_{i=l}^{r}a_i$) if and only if they pass each test case from $l$ to $r$, and $0$ otherwise.

Your goal is to choose a way to partition the $m$ test cases into groups so that the total score obtained by all contestants is minimized. For each $i$ with $1\le i \le S$, determine the minimum possible total score when you partition the test cases into exactly $i$ groups.

Formally, let $f(l, r)$ be the number of contestants who pass all test cases in the interval $[l, r]$, and let $P(l, r)=\sum_{j=l}^{r} a_j$. Then if you partition the tests into intervals $[t_1, t_2], [t_2+1, t_3], \ldots, [t_{k}+1, m]$ (with $t_1=1$ and $t_{k+1}=m$), the total score is given by: [ \text{Total Score} = \sum_{\text{each group }[l, r]} f(l,r)\times P(l,r). ]

You need to output $S$ numbers where the $i$-th number is the minimum total score when the $m$ test cases are partitioned into $i$ groups.

Note: All formulas are in (\LaTeX) format.

inputFormat

The first line contains three integers: n m S — the number of contestants, the number of test cases, and the number of groups queries respectively.

The second line contains m integers a1, a2, ..., am, where ai denotes the score for test case i.

Then follow n lines. Each of these lines is a binary string of length m consisting of characters '0' and '1'. The j-th character of the i-th line is '1' if the i-th contestant passes test case j, and '0' otherwise.

outputFormat

Output exactly S integers separated by spaces (or on separate lines). The i-th integer should be the minimum possible total score over all contestants when partitioning the test cases into exactly i contiguous groups.

sample

2 3 2
1 2 3
111
101

6 7