Description：

Solution：

Code：

#include<algorithm>

#include<iostream>

#include<cstdlib>

#include<cstdio>

#include<cmath>

#include<queue>

#include<cstring>

#define INF 0x3f3f3f3f

using namespace std;

int n,m;

#define MAXN 41

#define MAXM 110

int p[MAXN];

int c[MAXN][MAXM];

int now[MAXM];

int sum = 0;

struct edge

{

	int to,nxt,f,c;

}e[1000010];

int edgenum = 0;

int lin[81000];

#define MAXP 80101

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

{

	e[edgenum].to = b;e[edgenum].c = c;e[edgenum].f = f;e[edgenum].nxt = lin[a];lin[a] = edgenum++;

	e[edgenum].to = a;e[edgenum].c = -c;e[edgenum].f = 0;e[edgenum].nxt = lin[b];lin[b] = edgenum++;

	return;

}

int s,t;

inline int to(int x,int y){return (x - 1) * sum + y + n;}

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

bool v[MAXP];

int q[1000000];

inline bool SPFA()

{

	memset(d,0x3f,sizeof(d));

	memset(v,0,sizeof(v));

	register int head = 1,tail = 0;

	q[++tail] = s;

	d[s] = 0;

	v[s] = true;

	rate[s] = INF;

	while(head <= tail)

	{

		register int k = q[head++];

		v[k] = false;

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

		{

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

			{

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

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

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

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

				{

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

					q[++tail] = e[i].to;

				}

			}

		}

	}

	return (d[t] < 0x3f3f3f3f);

}

inline int read()

{

	register int res = 0;

	register char c = getchar();

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

	while(isdigit(c))

	{

		res = (res << 1) + (res << 3) + c - '0';

		c = getchar();

	}

	return res;

}

int main()

{

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

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

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

	{

		p[i] = read();

		sum += p[i];

	}

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

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

		add(s,i,0,p[i]);

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

	{

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

		{

			c[i][j] = read();

			add(i,to(j,1),c[i][j],1);

			now[j] = 1;

		}

	}

	for(register int i = 1;i <= m;++i)

	{

		add(to(i,1),t,0,1);

	}

	int ans = 0;

	register int a;

	int k = 0;

	while(SPFA())

	{

		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];

		}

		ans += rate[t] * d[t];

		if(++k >= sum)break;

		a = e[pre[t] ^ 1].to;

		a = (a - n) / sum + 1;

		add(to(a,++now[a]),t,0,1);

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

		{

			add(i,to(a,now[a]),c[i][a] * now[a],1);

		}

	}

	printf("%d\n",ans);

	return 0;

}