[POJ1038]Bugs Integrated, Inc.

Grade Open Time Friday, 19 September 2014, 10:08 am
Discount 0.8 Time Discount Friday, 26 September 2014, 10:08 am
Allow late Yes Close Time Friday, 26 September 2014, 10:08 am
Input file exameight.in Output file exameight.out

【英文原题】

Bugs Integrated, Inc. is a major manufacturer of advanced memory chips. They are launching production of a new six terabyte Q-RAM chip. Each chip consists of six unit squares arranged in a form of a 2*3 rectangle. The way Q-RAM chips are made is such that one takes a rectangular plate of silicon divided into N*M unit squares. Then all squares are tested carefully and the bad ones are marked with a black marker.


Finally, the plate of silicon is cut into memory chips. Each chip consists of 2*3 (or 3*2) unit squares. Of course, no chip can contain any bad (marked) squares. It might not be possible to cut the plate so that every good unit square is a part of some memory chip. The corporation wants to waste as little good squares as possible. Therefore they would like to know how to cut the plate to make the maximum number of chips possible.
Task

You are given the dimensions of several silicon plates and a list of all bad unit squares for each plate. Your task is to write a program that computes for each plate the maximum number of chips that can be cut out of the plate.


【题目描述】


给出n*m(n≤150,m≤10)的棋盘,要在上面放置2*3 的骨牌,有一些方格无法放置,求最多能放置多少个。


【输入格式】

输入包含多组数据。

输入文件第一行是数据组数T(T<=50)。

接下来是T组数据。

每组数据的第一行有三个正数n,m,k,其中k是无法放置骨牌的格子个数。

接下来有k行,每行两个整数(x,y),表示格子(x,y)无法放置骨牌。

【输出格式】

对每组数据,输出一行一个正整数,即最多放置的骨牌个数。

【样例输入】

2
6 6 5
1 4
4 6
2 2
3 6
6 4
6 5 4
3 3
6 1
6 2
6 4

【样例输出】

3
4

【来源】

北京大学 POJ 1038