#3022. 「CQOI2017」老 C 的方块

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

题目描述

老 C 是个程序员。

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

下图所示是一个 R=C=8R=C=8 的网格,蓝色标注的边是特殊边。首先,在第 11 行,第 11 列和第 22 列之间有一条特殊边。因为竖直方向周期为 22 ,所以所有的奇数行,第 11 列和第 22 列之间都有特殊边。因为水平方向周期为 44 ,所以所有奇数行的第 55 列和第 66 列之间也有特殊边,如果网格足够大,所有奇数行的第 99 列和第 1010 列、第 1313 列和第 1414 列之间都有特殊边。因为所有的奇数列和下一列之间都有特殊边,所以第 33 列和第 44 列、第 77 列和第 88 列之间也有特殊边,而所在行的编号从左到右奇偶交替,所以它们的特殊边在偶数行。如果网格的规模更大,我们可以用同样的方法找出所有的特殊边。

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

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

输入格式

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

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

输出格式

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

样例

样例输入 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

数据范围与提示

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

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

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

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