A5883 | 「CEOI2016」Popeala

**译自 [CEOI2016](http://www.ceoi2016.ro/) Day2 T2「[Popeala](http://ceoi.inf.elte.hu/probarch/16/popeala-statement.pdf)」**

> 罗马尼亚语中的「popeală」一词起源于一篇罗马尼亚历史短篇小说 [*Alexandru Lăpuşneanul*](https://ro.wikipedia.org/wiki/Alexandru_L%C4%83pu%C8%99neanul_(nuvel%C4%83))，这篇小说中用 Moldavia 王子的口吻，用这个词的变体描述了他将对篡位者进行的报复行动。这个词最近在罗马尼亚程序竞赛中复活了，有点令人惊讶。它用来描述科学委员会用一些非正统并且（通常）非自愿的方式让选手生活更难的一切情况：十分严格的时间限制，不合法的输入数据，错误的题面，偷键盘或者其他诸如此类的外设。
>
> 这是有关「popeală」的一道题。

考虑一场有 $N$ 个选手参加的程序设计竞赛。比赛只有一道题，这道题有 $T$ 组测试数据。科学委员会想要把这些数据组成最多 $S$ 个子任务。

**子任务如何工作**：每组测试数据将会属于**恰好一个**子任务中。一个子任务可以包含任意数量的测试数据，但它不能为空。如果一个选手没有通过某个子任务中的**任一**测试数据，这个选手在这个子任务中将获得 $0$ 分。否则，这个子任务的得分将等于子任务内所有测试数据的得分之和。

这是程序设计竞赛中的通常实践，但问题是科学委员会想要在**比赛之后**做这件事。他们知道每一个选手正确解出了哪些测试点，它们想要把这些测试点组成子任务，以**最小化比赛中选手获得分数的和**。

具体来说，给你一个大小为 $T$ 的整数数组 $\texttt{Points[]}$。$\texttt{Points[i]}$ 是第 $i$ 组数据的得分。同样给你一个大小为 $N\times T$ 的二维数组 $\texttt{Results[][]}$。如果第 $i$ 个选手正确解决了第 $j$ 组测试数据，那么 $\texttt{Results[i][j]}$ 等于 $1$，否则等于 $0$。并且委员会决定所有的子任务将包含一些**连续的测试数据**。换句话说，如果测试数据 $X$ 和 $Y$ 将出现在同一子任务中，那么对于所有测试数据 $Z$，满足 $X\le Z\le Y$ 的测试数据同样必须属于这个子任务。

你需要帮助委员会。他们想知道，对于每个 $1\le K\le S$，如果恰好把测试数据分为 $K$ 个子任务的话，选手获得分数和的最小值是多少。

第一行包含三个整数 $N,T,S$。

第二行包含 $T$ 个整数，表示数组 $\texttt{Points[]}$ 中的元素。

接下来 $N$ 行，每行一个长度为 $T$ 的 $01$ 串，表示二维数组 $\texttt{Results[][]}$ 中的元素。

输出 $S$ 行，第 $i$ 行包含一个整数，表示如果测试数据被分为 $i$ 个子任务的话选手得分之和的最小值。