题目背景

ZRQ在洞穴中准备采集矿物的时候遇险了！洞穴要塌了！

题目来源：zhoutb2333

题目描述

整个洞穴是一个$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$个方向）。

柱子占据相邻的格子不会降低其不稳定度（换句话说就是柱子只有在拐角处有力量）。

有些格子的顶已经塌下来了，无法在其位置放置柱子了，这些格子也不能被占据了。这样已经塌了的格子有$K$个（他们的不稳定度都为$0$,即使$X+Y$为奇数，塌下来的格子的不稳定度也会为$0$）。

ZRQ想问你，在放置一些柱子后 ，最小的不稳定度之和为多少（可以不将$M$个柱子都放完）。

输入格式

第一行三个整数$N,M,K$

接下来$N$行每行$N$个整数，表示每个格子的不稳定度，保证$X+Y$为偶数的格子和已经塌下的格子的不稳定度为$0$。

接下来$K$行每行$2$个整数$X,Y$，表示已经塌下的格子的坐标。

输出格式

一行一个整数，表示最小的不稳定度的和。

3 3 1
0 1 0
2 0 1
0 1 0
1 3

3

3 3 4
0 2 0
0 0 4
0 3 0
1 3
2 1
2 2
3 1

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$。