题目描述

译自 CEOI2016 Day2 T2「Popeala」

罗马尼亚语中的「popeală」一词起源于一篇罗马尼亚历史短篇小说 Alexandru Lăpuşneanul，这篇小说中用 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$ 个子任务的话选手得分之和的最小值。

2 3 3
4 3 5
101
110

0
8
16

数据范围与提示

对于全部数据，$1\le T\le 2\times 10^4,1\le N\le 50,1\le S\le \min(50,T)$。

保证对于所有 $1\le i\le T$，都有 $1\le \texttt{Points[i]}\le 10^4$，且对于所有数据，$N\cdot(\texttt{Points[1]}+\texttt{Points[2]}+\ldots +\texttt{Points[T]})\le 2\times 10^9$。

• 对于其中 $8$ 分的数据，$T\le 40$；
• 对于另外 $9$ 分的数据，$40<T\le 500$；
• 对于另外 $9$ 分的数据，$500<T\le 4\times10^3$。

你写过的任何代码都可能被用来让你拿到更低的分数。（开个玩笑）