Bugs Integrated, Inc.
Time Limit:15000MS  Memory Limit:30000K
Total Submit:1180 Accepted:309
Case Time Limit:5000MS

Description
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.

Input
The first line of the input file consists of a single integer D (1 <= D <= 5), denoting the number of silicon plates. D blocks follow, each describing one silicon plate. The first line of each block contains three integers N (1 <= N <= 150), M (1 <= M <= 10), K (0 <= K <= MN) separated by single spaces. N is the length of the plate, M is its height and K is the number of bad squares in the plate. The following K lines contain a list of bad squares. Each line consists of two integers x and y (1 <= x <= N, 1 <= y <= M) ?coordinates of one bad square (the upper left square has coordinates [1, 1], the bottom right is [N,M]).

Output
For each plate in the input file output a single line containing the maximum number of memory chips that can be cut out of the plate.

Sample Input

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

Sample Output

3
4

Source
CEOI 2002

CODE:

#include <iostream>
using namespace std;

int g[150][10], blk[10];
int d[4][60000];
int e[11] = {1, 3, 9, 27, 81, 243, 729, 2187, 6561, 19683, 59049};
int n, m, kn;
int can1, can2, b[10][60000];
int *l0, *l1, *l2, *l3, *bit0, *bit1, *bit2;

void build() {
    int i, j, tmp;
    for (i=0; i<e[10]; i++) {
        j = 0; tmp = i;
        while (tmp > 0) {
            b[j][i] = tmp % 3;
            tmp /= 3;
            j++;
        }
    }
} 

inline int maxt(int a, int b) {
    return a > b ? a : b;
}

void solve() {
    int i, j, k, x, y, a1, a2, p, c;
    scanf("%d%d%d", &n, &m, &kn);
    memset(g, 0, sizeof(g));
    memset(d, 0, sizeof(d));
    for (i=0; i<kn; i++) {
        scanf("%d%d", &x, &y);
        g[x-1][y-1] = 1;
    }
    for (i=0; i<m; i++) blk[i] = 1 - g[0][i];
    for (i=1, c=2; i<n; i++) {
        for (j=0; j<m; j++) {
            if (g[i][j]) blk[j] = 0;
            else blk[j]++;
            c = (c+1)%4;
            can1 = (j>0 && blk[j]>2 && blk[j-1]>2);
            can2 = (j>1 && blk[j]>1 && blk[j-1]>1 && blk[j-2]>1);
            a1 = 2*e[j]+2*e[j-1];
            a2 = e[j]+e[j-1]+e[j-2];
            l0 = d[c]; l1 = d[(c+3)%4]; l2 = d[(c+2)%4]; l3 = d[(c+1)%4];
            bit0 = b[j]; 
            if (j>0) bit1 = b[j-1]; 
            if (j>1) bit2 = b[j-2];
            for (p=0; p<e[m]; p++) {
                if (bit0[p]) {
                    l0[p] = l1[p-e[j]];
                } else {
                    l0[p] = l1[p];
                    if (j>0 && !bit1[p]) {
                        if (can1) l0[p] = maxt(l0[p],l2[p+a1]+1);
                        if (can2 && !bit2[p]) l0[p] = maxt(l0[p], l3[p+a2]+1);
                    }
                }
            }
        }
    }
    printf("%d\n", d[c][0]);
}

int main() {
    build();
    int caseTime;
    scanf("%d", &caseTime);
    while (caseTime--) {
        solve();
    }
    return 0;
}