#3022. 「CQOI2017」老 C 的方块

内存限制:128 MiB 时间限制:1000 ms 标准输入输出
题目类型:传统 评测方式:文本比较
上传者: M_sea

题目描述

老 C 是个程序员。

作为一个懒惰的程序员,老 C 经常在电脑上玩方块游戏消磨时间。游戏被限定在一个由小方格排成的 R C 列网格上,如果两个小方格有公共的边,就称它们是相邻的,而且有些相邻的小方格之间的公共边比较特殊。特殊的公共边排列得有很强的规律。首先规定,第 1 行的前两个小方格之间的边是特殊边。然后,特殊边在水平方向上每 4 个小方格为一个周期,在竖直方向上每 2 个小方格为一个周期。所有的奇数列与下一列之间都有特殊边,且所在行的编号从左到右奇偶交替。

下图所示是一个 R=C=8 的网格,蓝色标注的边是特殊边。首先,在第 1 行,第 1 列和第 2 列之间有一条特殊边。因为竖直方向周期为 2 ,所以所有的奇数行,第 1 列和第 2 列之间都有特殊边。因为水平方向周期为 4 ,所以所有奇数行的第 5 列和第 6 列之间也有特殊边,如果网格足够大,所有奇数行的第 9 列和第 10 列、第 13 列和第 14 列之间都有特殊边。因为所有的奇数列和下一列之间都有特殊边,所以第 3 列和第 4 列、第 7 列和第 8 列之间也有特殊边,而所在行的编号从左到右奇偶交替,所以它们的特殊边在偶数行。如果网格的规模更大,我们可以用同样的方法找出所有的特殊边。

网格的每个小方格刚好可以放入一个小方块,在游戏的一开始,有些小方格已经放上了小方块,另外的小方格没有放。老 C 很讨厌下图所示的图形,如果他发现有一些小方块排列成了它讨厌的形状(特殊边的位置也要如图中所示),就很容易弃疗,即使是经过任意次旋转、翻转后排列成讨厌的形状,老 C 也同样容易弃疗。

为了防止弃疗,老 C 决定趁自己还没有弃疗,赶紧移除一些格子里小方块,使得剩下的小方块不能构成它讨厌的形状。但是游戏里每移除一个方块都是要花费一些金币的,每个方块需要花费的金币有多有少参差不齐。老 C 当然希望尽可能少的使用游戏里的金币,但是最少要花费多少金币呢?老 C 懒得思考,就把这个问题交给你了。

输入格式

第一行有 3 个正整数 C,R,n ,表示 C R 行的网格中,有 n 个小方格放了小方块。

接下来 n 行,每行 3 个正整数 x,y,w ,表示在第 x 列第 y 行的小方格里放了小方块,移除它需要花费 w 个金币。保证不会重复,且都在网格范围内。

输出格式

输出一行,包含一个整数,表示最少花费的金币数量。

样例

样例输入 1

2 2 4
1 1 5 
1 2 6 
2 1 7 
2 2 8 

样例输入 1

5

样例输入 2

3 3 7 
1 1 10 
1 2 15 
1 3 10 
2 1 10 
2 2 10 
2 3 10 
3 1 10 

样例输出 2

15

数据范围与提示

对于第 1\sim2 个测试点, 1 ≤ C, R ≤ 100, 1 ≤ n ≤ 20

对于第 3\sim6 个测试点, 1 ≤ C, R ≤ 10^5, 2000 ≤ n ≤ 5000 ,数据有梯度;

对于第 7\sim10 个测试点, 1 ≤ C, R ≤ 10^5, 30000 ≤ n ≤ 10^5 ,数据有梯度;

对于所有测试点, 1 ≤ C, R, n ≤ 10^5, 1 ≤ w \leq 10^4