题目描述

译自 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

样例解释

有 $N=2$ 个选手，$T=3$ 组测试数据，并且 $S=3$，表示我们需要分别计算有 $1, 2, 3$ 个子任务时的最小分数。$\texttt{Points[]}$ 数组是 $\{4, 3, 5\}$。

如果只有一个子任务，那么可以得到的总分为 0，因为两个选手都没有正确通过全部测试数据，并且此时所有测试数据都在同一个子任务中。

有两种方法把这些数据分为两个子任务。其中一种分法最后的得分和为 12，另一种为 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 \times 10^3$。