Description：

$N\times N$ 的方格图， $i+j$ 为奇数的格子有不稳定度，有一些格子被封死了，在方格图中放不多于 $M$ 个 $L$ 型的柱子使得不被 $L$ 拐点覆盖的不稳定度最小。

$1 \le N \le 50$

Solution：

发现拐点一定放在奇数点上，那 $L$ 的两个分支一定放在列标号奇偶性不同的两个偶数格子上，考虑网络流构图，将一个 $L$ 型格子看成一个从原点到汇点的路径，不难想到把偶数格子按列标号奇偶性不同分成两列分别和原点与汇点连边，把奇数格子放在中间，把奇数格子拆成两个点，中间边的权值为负的不稳定度，跑最小费用最大流再加上 $sum$ 即可。

Code：

#include<algorithm>

#include<iostream>

#include<cstdlib>

#include<cstdio>

#include<cmath>

#include<queue>

#include<cstring>

using namespace std;

int n,m,k;

#define MAXN 51

int map[MAXN][MAXN];

#define MAXE 5000100

struct edge

{

	int to,nxt,f,c;

}e[MAXE];

int edgenum = 0;

int lin[MAXN * MAXN * 2];

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

{

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

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

	return;

}

bool c[MAXN][MAXN];

int s,t;

int to(int i,int j){return (i - 1) * n + j;}

#define TOTN (MAXN * MAXN * 2)

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

bool v[TOTN];

bool SPFA()

{

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

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

	memset(pre,0,sizeof(pre));

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

	queue<int> q;

	d[s] = 0;

	v[s] = true;

	q.push(s);

	while(!q.empty())

	{

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

		v[k] = false;

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

		{

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

			{

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

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

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

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

				{

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

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

				}

			}

		}

	}

	return (d[t] < 0x3f3f3f3f);

}

int flow()

{

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

}

int EK()

{

	int ans = 0,r,sum = 0;

	while(SPFA())

	{

		r = flow();

		sum += 1;

		if(sum > m || r >= 0)return ans;

		ans += r;

	}

	return ans;

}

int main()

{

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

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

	int sum = 0;

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

	{

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

		{

			scanf("%d",&map[i][j]);

			sum += map[i][j];

		}

	}

	s = 2 * n * n + 1;t = s + 1;

	int x,y;

	memset(c,0,sizeof(c));

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

	{

		scanf("%d%d",&x,&y);

		c[x][y] = true;

	}

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

	{

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

		{

			if(c[i][j])continue;

			if((i + j) % 2 == 0)

			{

				if(j % 2 == 1)

				{

					add(s,to(i,j),1,0);

					if(i > 1)add(to(i,j),to(i - 1,j),1,0);

					if(i < n)add(to(i,j),to(i + 1,j),1,0);

					if(j > 1)add(to(i,j),to(i,j - 1),1,0);

					if(j < n)add(to(i,j),to(i,j + 1),1,0);

				}

				else 

				{

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

					if(i > 1)add(to(i - 1,j) + n * n,to(i,j),1,0);

					if(i < n)add(to(i + 1,j) + n * n,to(i,j),1,0);

					if(j > 1)add(to(i,j - 1) + n * n,to(i,j),1,0);

					if(j < n)add(to(i,j + 1) + n * n,to(i,j),1,0);

				}

			}

			else

			{

				add(to(i,j),to(i,j) + n * n,1,-map[i][j]);

			}

		}

	}

	cout << sum + EK() << endl;

	return 0;

}