2640. Florid Banner

输入格式

The input consists of one or more test cases.

Each test case contains two parts.

The first part of the input describes the banner Mr. Murphy designed.

First line:

Two integers M (0<M<=10) and N (0<N<=10,000), describes the width and the length of the banner.

Second line:

One integer t states that the banner has t regions.

Following t lines:

Each line has 5 integers x1,y1,x2,y2,c, represents a region from (x1,y1), the left bottom corner, to (x2,y2), the right top corner, and the color type of this region is c.

The whole banner is M*N, with its left bottom located at (0, 0). It is guaranteed that t regions can exactly cover the whole banner once. (0<=x1<x2<=M, 0<=y1<y2<=N)

The second part describes the materials left in the store. No need to worry about the number of them, because they are infinity.

The first line:

The number of materials fn(0<=fn<=10000)

Following fn lines:

Each line represents one kind of material. Following an integer P(P>0) indicates the price, and an integer L(1<=L<=20) indicates the length of this banner. Then L integers for this material, i-th number indicates the color at position range from (0,i-1) to (1,i).

You may assume that the number of colors is no more than 30.

Input will be terminated by EOF.

输出格式

For each test case, output one line represents the minimum cost of the banner, or ‘impossible’ if Adam can’t make one anyhow.

Hint

The pattern of the sample is as follows:

2 5
7
0 0 2 1 0
1 1 2 3 0
0 1 1 2 1
0 2 1 3 2
0 3 2 4 1
0 4 1 5 3
1 4 2 5 2
5
1 3 0 0 0
2 3 2 1 3
2 3 0 1 2
1 2 1 3
5 1 0

15