Description：

$n$ 个人报名小组，每人每次报名第 $i$ 个小组花费 $F_i$ ，每个人不能参加超过 $k$ 个小组，如果有 $x$ 个人报名第 $i$ 个小组获得 $c_i\times x^2$ ，在最大化参加人数的前提下最小化收益 $-$ 花费。

$1\leqslant n\leqslant 100$

Solution：

如果要最大化参加人次的话那就是一个裸的费用流了，但是要最大化参加人数，那么就不太好做了。

但是我们考虑一个经典思路，正难则反，我们可以先给每个人选 $k$ 个，然后只给每个人 $k-1$ 次撤销的机会，就能保证参加人数最多了，每个人都一定参加了一个小组。

于是建图就很好办了，从源点向每个点连容量为 $k$ 费用为 $0$ 的边，每个点向汇点连容量为 $k-1$ 费用为 $0$ 的边，每个人向小组 $i$ 连容量为 $1$ 费用为 $F_i$ 的边，由于权值是平方，我们可以连若干条 $c_i\times 1,c_i\times 3,c_i\times 5,\dots$ ，这样按顺序流过去得到的就是平方了。

Code：

#include<algorithm>

#include<iostream>

#include<cstdlib>

#include<cstdio>

#include<cmath>

#include<queue>

#include<cctype>

#include<cstring>

using namespace std;

inline int getc()

{

	register char c = getchar();

	while(!isdigit(c))c = getchar();

	return c - '0';

}

int n,m,p;

#define MAXN 110

int c[MAXN],f[MAXN];

int s,t;

#define MAXP MAXN * 2

#define MAXE (MAXN * MAXN * 2 + MAXN * 2)

struct edge

{

    int to,nxt,f,v;

}e[MAXE << 1];

int edgenum = 0;

int lin[MAXP];

inline void add(int a,int b,int c,int d)

{//cout << a << " " << b << " " << c << " " << d << endl;

    e[edgenum] = (edge){b,lin[a],c,d};lin[a] = edgenum++;

    e[edgenum] = (edge){a,lin[b],0,-d};lin[b] = edgenum++;

    return;

}

int d[MAXP],rate[MAXP],pre[MAXP];

bool v[MAXP];

#define INF 0x3f3f3f3f

inline bool SPFA()

{

    memset(d,0x3f,sizeof(d));d[s] = 0;

    queue<int> q;q.push(s);

    rate[s] = INF;

    while(!q.empty())

    {

        register int k = q.front();q.pop();

        v[k] = false;

        for(register int i = lin[k];i != -1;i = e[i].nxt)

        {

            if(d[e[i].to] > d[k] + e[i].v && e[i].f)

            {

                d[e[i].to] = d[k] + e[i].v;

                rate[e[i].to] = min(rate[k],e[i].f);

                pre[e[i].to] = i;

                if(!v[e[i].to])

                {

                    v[e[i].to] = true;

                    q.push(e[i].to);

                }

            }

        }

    }

    return d[t] < INF;

}

inline int flow()

{

    for(register int i = t;i != s;i = e[pre[i] ^ 1].to)

    {

        e[pre[i]].f -= rate[t];

        e[pre[i] ^ 1].f += rate[t];

    }

    return rate[t] * d[t];

}

inline int EK()

{

    register int ans = 0;

    while(SPFA())ans += flow();

    return ans; 

}

int main()

{

	memset(lin,-1,sizeof(lin));

	scanf("%d%d%d",&n,&m,&p);

	for(int i = 1;i <= m;++i)scanf("%d",&c[i]);

	for(int i = 1;i <= m;++i)scanf("%d",&f[i]);

	s = n + m + 1;t = s + 1;

	for(int i = 1;i <= m;++i)for(int j = 1;j <= n;++j)add(i + n,t,1,c[i] * (2 * j - 1));

	for(int i = 1;i <= n;++i)add(s,i,p,0),add(i,t,p - 1,0);

	for(int i = 1;i <= n;++i)

	{

		int x;

		for(int j = 1;j <= m;++j)

		{

			x = getc();

			if(x)add(i,j + n,1,-f[j]);

		}

	}

	cout << EK() << endl;

	return 0;

}