#P5403. [2018年湖南省队集训]marshland
[2018年湖南省队集训]marshland
marshland
题目描述
用一个 的网格表示沼泽地。第 行第 列的格子记为 ,左上角为 ,右下角为 。 为奇数的格子有危险度 ,其余格子的危险度为 。
你有 块 L 形石头。每块石头占据同一个 方块中的三个格子,可以旋转到四种朝向。每块石头只会把它拐角所在格子的危险度变为 。石头占据的格子不能重叠。
网格上有 条禁止位置记录。石头的任何部分都不能放在禁止位置上。禁止位置的危险度为 。
可以放置至多 块石头。求放置后所有格子的危险度之和的最小值。
输入格式
第一行三个整数 。
接下来 行,每行 个整数,表示各格子的危险度。 为偶数的格子和禁止位置的危险度保证为 。
接下来 行,每行两个整数 ,表示一个禁止位置。记录可能重复。
输出格式
输出一行一个整数,表示危险度之和的最小值。
样例
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
补充样例 3
2 1 0
0 7
4 0
4
把一块石头的拐角放在危险度为 的格子上,其余两格分别为左侧与下侧的零危险格,剩余危险度为 。
数据范围
- 对于 的数据,。
- 对于 的数据,。
- 对于 的数据,。
对于所有数据,,,。