Description

你办了一场比赛，有n给人参加，只有一道题，有m个数据点，标号为1~m，每个测试点都有一个分数a[i]。现在所

有选手已经提交了程序并且测评完了，你知道每个人都能通过哪些测试点。你现在要安排捆绑测试的方式，把数据

点划分为若干个连续的区间，每个区间至少有一个测试点。每个区间只要有一个测试点错误就不会得分，如果所有

点都正确得分为所有测试点的分数的和。你的目的是最小化所有人的得分和。你需要对1<=i<=S，输出当把所有测

试点划分为i组时，最小的所有人分数和。

Format

Input

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

接下来一行m个整数，代表a[i]

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

n<=50

m<=200000

S<=min(50,m)

a[i]<=10000,sigma a[i]*n<=2000000000

Output

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

Samples

123 500

0
8
16