洞穴遇险
题目背景
**ZRQ**在洞穴中准备采集矿物的时候遇险了!洞穴**要塌了**!
题目来源:[zhoutb2333](https://www.luogu.org/space/show?uid=31564)
题目描述
整个洞穴是一个$N*N$的方格图,每个格子形如$(X,Y),1 \le X,Y \le N$。其中$X$表示从上到下的行数,$Y$表示从左到右的列数。$(1,1)$在左上角,$(1,N)$在右上角,$(N,1)$在左下角,$(N,N)$在右下角。
满足$X+Y$为奇数格子的有一个不稳定度$V_{X,Y},X+Y$为偶数的格子的不稳定度为$0$。
**ZRQ**现在手里恰巧有$M$个可以支撑洞穴的柱子,柱子的力量可以认为是无穷大。
只要支撑住了一个格子那么这个格子的不稳定度将降为$0$。
每个柱子是$L$型的,它除了要占据当前的格子外,还需要占据两个相邻的格子(这三个格子形成$L$型,可以选择任意方向放置,一共有$4$个方向)。
![](https://cdn.luogu.com.cn/upload/pic/13049.png)
**柱子占据相邻的格子不会降低其不稳定度(换句话说就是柱子只有在拐角处有力量)**。
有些格子的顶已经塌下来了,无法在其位置放置柱子了,这些格子也不能被占据了。这样已经塌了的格子有$K$个(他们的不稳定度都为$0$,**即使$X+Y$为奇数,塌下来的格子的不稳定度也会为$0$**)。
**ZRQ**想问你,在放置一些柱子后 ,最小的不稳定度之和为多少(可以不将$M$个柱子都放完)。
输入输出格式
输入格式
第一行三个整数$N,M,K$
接下来$N$行每行$N$个整数,表示每个格子的不稳定度,**保证$X+Y$为偶数的格子和已经塌下的格子的不稳定度为$0$**。
接下来$K$行每行$2$个整数$X,Y$,表示已经塌下的格子的坐标。
输出格式
一行一个整数,表示最小的不稳定度的和。
输入输出样例
输入样例 #1
3 3 1
0 1 0
2 0 1
0 1 0
1 3
输出样例 #1
3
输入样例 #2
3 3 4
0 2 0
0 0 4
0 3 0
1 3
2 1
2 2
3 1
输出样例 #2
9
说明
共$10$个测试点,每个点$10$分,计$100$分。
对于测试点$1$~$3$,有$1 \le N \le 6$
对于测试点$4$~$7$,有$1 \le N \le 11$
对于测试点$8$~$10$,有$1 \le N \le 50$
对于所有测试点,$0 \le M \le \frac{N^2}{3}, 0 \le K \le N^2, 0 \le V_{X,Y} \le 10^6$
**样例#1解释:**
显然无法让任意两个不稳定的格子都被拐角覆盖,于是将$(2,1)$用拐角覆盖住即可。这样剩余的不稳定度为$V_{1,2}+V_{2,3}+V_{3,2}=1+1+1=3$。
**样例#2解释:**
一个都放不下,这样剩余的不稳定度为$V_{1,2}+V_{2,3}+V_{3,2}=2+4+3=9$。