罗马尼亚语单词 "popeală" 源自罗马尼亚历史中篇小说《亚历山德鲁·勒普什内亚努》(Alexandru Lăpușneanul)，同名的摩尔达维亚大公用该词的一个变体来描述他即将对篡位者进行的复仇。这个词最近在罗马尼亚的编程竞赛圈中意外地复兴了。它被用来描述科学委员会以一种非正统且（通常是）非自愿的方式让参赛者生活变得更加困难的任何情况：非常严格的时间限制、无效的测试用例、错误的题目描述、偷走键盘以及其他类似的手段。本题就是关于这样一种 "popeală"。

考虑一场有 $N$ 名参赛者的编程竞赛。该竞赛只有一个题目，包含 $T$ 个测试用例。科学委员会希望将这些测试用例分为最多 $S$ 个子任务。

子任务的工作方式如下：每个测试用例将属于且仅属于一个子任务。一个子任务可以包含任意数量的测试用例，但不能为空。如果一名参赛者未能通过某个子任务中的任何一个测试用例，那么他/她在该子任务上的得分将为 $0$。否则，该子任务的得分将等于其所有测试用例分值之和。

这是编程竞赛中的常见做法，但问题在于科学委员会希望在竞赛结束后才进行分组。他们知道每位参赛者正确解决了哪些测试用例，并且他们希望将测试用例分组，以最小化竞赛中参赛者获得的总分数。

具体来说，给定一个大小为 $T$ 的整数数组 Points[]。Points[i] 包含第 $i$ 个测试用例的分值。此外，还给定一个大小为 $N \times T$ 的二维数组 Results[][]。如果第 $i$ 名参赛者正确解决了第 $j$ 个测试用例，则 Results[i][j] 等于 $1$。否则，它等于 $0$。委员会已经决定，所有子任务都将包含连续的测试用例。换句话说，如果测试用例 $X$ 和 $Y$ 被分在同一个子任务中，那么对于所有满足 $X \le Z \le Y$ 的测试用例 $Z$，也必须属于该子任务。

你需要帮助委员会。他们想知道，对于每个 $1 \le K \le S$，如果他们选择将测试用例恰好分为 $K$ 个子任务，那么竞赛中可能获得的最小总分数是多少。

输入格式

输入文件 popeala.in 的第一行包含三个用空格分隔的正整数：$N, T, S$。第二行包含 $T$ 个用空格分隔的正整数，表示 Points[] 数组的元素。接下来的 $N$ 行，每行包含一个长度为 $T$ 的二进制字符串，表示 Results[][] 矩阵的元素。

输出格式

输出文件 popeala.out 应包含 $S$ 行。第 $i$ 行应包含一个整数：如果将测试用例分为 $i$ 个子任务，竞赛中可能获得的最小总分数。

数据范围

• $1 \le T \le 20\,000$
• $1 \le N \le 50$
• $1 \le S \le \min(50, T)$
• 对于所有 $1 \le i \le T$，$1 \le \text{Points}[i] \le 10\,000$。此外，保证对于所有测试用例，$(\text{Points}[1] + \dots + \text{Points}[T]) \times N \le 2\,000\,000\,000$。
• 对于分值为 8 分的测试用例，$T \le 40$。
• 对于分值为另外 9 分的测试用例，$40 < T \le 500$。
• 对于分值为另外 9 分的测试用例，$500 < T \le 4\,000$。
• 你编写的任何代码都可能被用来对付你。

样例

输入 1

2 3 3
4 3 5
101
110

输出 1

0
8
16

说明 1

这里有 $N = 2$ 名参赛者，$T = 3$ 个测试用例，$S = 3$，这意味着我们必须分别计算 $1, 2$ 和 $3$ 个子任务时的最小分数。Points[] 数组为 $\{4, 3, 5\}$。

在单个子任务的情况下，可获得的总分数为 $0$，因为没有参赛者正确解决了所有测试用例，且所有测试用例必须在同一个子任务中。

将测试用例分为两个子任务有两种方式。其中一种产生的总分为 $12$ 分，另一种为 $8$ 分。因为我们寻求最小化该值，所以我们选择后者。

将测试用例分为三个子任务只有一种方式，产生的总分为 $16$ 分。