#include<bits/stdc++.h>
#define debug(x) cerr << #x << " " << x << "\n"
#define debugs(x) cerr << #x << " " << x << " "
#pragma GCC optimize("Ofast")
#define int long long
using namespace std;
mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
int range_rng(int l, int r)
{
return uniform_int_distribution<int>(l,r)(rng);
}
bool got[55][20005];
int score[20005];
int dp[20005][55];
int prefmin[55][20005];
int sp[20005];
int banned[55];
int last[55];
pair<int,int> er[20005][55];
vector<int> vals[20005];
int n;
const int inf=1e10;
int count_rows(int l, int r)
{
int re,pas;
re=0;
pas=(1<<5);
while (pas)
{
if (re+pas<vals[r].size() && vals[r][re+pas]<l)
re+=pas;
pas=pas/2;
}
if (vals[r][re]<l)
return re+1;
else
return 0;
}
signed main()
{
/*
ifstream fin("arbore.in");
ofstream fout("arbore.out");
*/
ios_base::sync_with_stdio(0);
cin.tie(0);
cout.tie(0);
int t,s,i,j,k,ceva,previ,r,sum,finished,x,pas;
bool ok;
string nush;
cin >> n >> t >> s;
for (i=1; i<=t; i++)
cin >> score[i];
sp[0]=0;
for (i=1; i<=t; i++)
sp[i]=sp[i-1]+score[i];
for (i=1; i<=n; i++)
{
cin >> nush;
for (j=0; j<nush.size(); j++)
{
if (nush[j]=='0')
got[i][j+1]=0;
else
got[i][j+1]=1;
}
}
for (i=1; i<=t; i++)
{
for (k=1; k<=n; k++)
{
if (!got[k][i])
last[k]=i;
vals[i].push_back(last[k]);
}
sort(vals[i].begin(),vals[i].end());
}
for (i=1; i<=t; i++)
{
for (j=1; j<=s; j++)
dp[i][j]=inf;
}
for (i=0; i<=t; i++)
{
for (j=0; j<=n; j++)
{
prefmin[j][i]=inf;
}
}
dp[0][0]=0;
sum=0;
for (i=1; i<=t; i++)
{
for (k=1; k<=n; k++)
{
if (banned[k])
continue;
if (!got[k][i])
{
sum-=sp[i-1];
banned[k]=1;
}
else
sum+=score[i];
}
dp[i][1]=sum;
}
for (i=1; i<=t; i++)
{
for (x=0; x<=n; x++)
{
er[i][x].first=-1;
er[i][x].second=0;
}
}
for (j=2; j<=s; j++)
{
for (x=0; x<=n; x++)
{
prefmin[x][0]=inf;
for (i=1; i<=t; i++)
prefmin[x][i]=min(prefmin[x][i-1],dp[i][j-1]-sp[i]*x);
}
for (i=1; i<=t; i++)
{
for (x=n; x>=0; x--)
{
if (er[i][x].first==-1)
{
r=i;
pas=(1<<14);
while (pas)
{
if (r-pas>=0 && count_rows(r-pas+1,i)>x)
r-=pas;
pas=pas/2;
}
er[i][x].first=r;
if (r!=0 && count_rows(r,i)==x)
{
dp[i][j]=min(dp[i][j],prefmin[x][r-1]+sp[i]*x);
er[i][x].second=1;
}
}
else
{
if (er[i][x].second==1)
{
r=er[i][x].first;
dp[i][j]=min(dp[i][j],prefmin[x][r-1]+sp[i]*x);
}
}
}
}
}
for (j=1; j<=s; j++)
cout << dp[t][j] << "\n";
return 0;
}
