You cannot submit for this problem because the contest is ended. You can click "Open in Problem Set" to view this problem in normal mode.

####【题目描述】

这一次，你是出题人。 你出好了一道题，并且收到了 $n$ 个人的源代码。你的这道题有 $m$ 个数据点，编号为 $1\cdots m$ ，第 $i$ 个数据点的分值为 $a_i$ 。

现在，你已经评测过一遍所有人的源代码，知道了每个人的代码分别通过了哪些测试点。接下来，你要把这道题改为捆绑测试，即把m个数据点划分为若干连续区间，这个区间的得分为其包含的测试点的分值总和，测试时，只有通过区间内所有的测试点，才能获得这个区间的得分。

作为出题人的你，想要最小化所有人的得分的总和。给定一个 $S$ ，对于 $1\le i\le S$ 的每个 $i$ ，你要求出当把所有测试点划分为刚好 $i$ 个区间时，最小的所有人的得分总和。 ####【输入格式】

第一行三个整数 $n,m,S$ 。

第二行 $m$ 个整数，表示 $a_1\cdots a_m$ 。

接下来 $n$ 行，每行一个长度为 $m$ 的 $01$ 串，表示第 $i$ 个人是否通过了第 $j$ 个测试点， $1$ 表示通过， $0$ 表示未通过。 ####【输出格式】 $S$ 行，每行一个整数，表示当把所有测试点划分为刚好 $i$ 个区间时，最小的所有人的得分总和。 ####【样例输入】

2 3 3
4 3 5
101
110

####【样例输出】

0
8
16

####【数据范围】

对于 $20\%$ 的数据， $m\le 14$

对于 $40\%$ 的数据， $m\le 100$

对于 $60\%$ 的数据， $m\le 500$

对于 $100\%$ 的数据， $n\le 50$,$m<=20000$ ， $S<=min(50,m)$

对于 $100\%$ 的数据， $a[i]<=10^4$ ，$(a[1]+a[2]+...+a[m]) * n <= 2 * 10^9$ 。