2640. Florid Banner

单点时限: 3.0 sec

内存限制: 256 MB

Adam C. Murphy loves shopping. One day, when he was wandering along the avenue, he discovered several stores with florid banners. (A 2*5 example is shown below)

He found them fantastic and decided to get one in order to decorate his fresh new house. Unfortunately, no one meets Adam’s requirement, after visiting all stores nearby. What was worse, all banners left in the stores are only those whose width is one. So he decided to make one himself by sewing them together.

Adam wants to make a banner exactly as he designed. He didn’t want to flip or rotate the materials he had, since he believed that keep it in its original way is more beautiful. And he didn’t want to cut the banners for the same reason.

Each material had different prices, so he wants to make his florid banner with minimum cost.

输入格式

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:

样例

Input
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
Output
15

0 人解决,2 人已尝试。

0 份提交通过,共有 6 份提交。

9.9 EMB 奖励。

创建: 11 年前.

修改: 2 年,11 月前.

最后提交: 3 周,4 天前.

来源: 多校联合比赛BNU站

题目标签