题目描述

你办了一场比赛，有 $n$ 个人参加，只有一道题，有 $m$ 个数据点，标号为 $1\sim m$，每个测试点都有一个分数 $a_i$。

现在所有选手已经提交了程序并且测评完了，你知道每个人都能通过哪些测试点。

你现在要安排捆绑测试的方式，把数据点划分为若干个连续的区间，每个区间至少有一个测试点。每个区间只要有一个测试点错误就不会得分，如果所有 点都正确得分为所有测试点的分数的和。

你的目的是最小化所有人的得分和。你需要对 $1\le i\le S$，输出当把所有测试点划分为 $i$ 组时，最小的所有人分数和。

输入格式

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

接下来一行 $m$ 个整数，代表 $a_i$。

接下来 $n$ 行每行一个长度为 $m$ 的 $01$ 串，代表第 $i$ 个人是否通过了第 $j$ 个测试点。

输出格式

$S$ 行，每行一个整数，代表当划分为 $i$ 个捆绑测试点时所有人分数和的最小值。

2 3 3
4 3 5
101
110

0
8
16

提示

对于 $100\%$ 的数据，$1\le n\le 50$，$1\le m\le 2\times 10^4$，$S\le \min(50,m)，1\le a_i \le 10^4$，$\Sigma a_i\times n\le 2\times10^9$。