21909_FloridBanner

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 only have width 1. 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 x₁, y₁, x₂, y₂, c, represents a region from (x₁, y₁), the left bottom corner, to (x₂, y₂), 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 ≤ x₁ < x₂ ≤ M ,  0 ≤ y₁ < y₂ ≤ 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 f_n ( 0 ≤ f_n ≤ 10000 )

Following f_n 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.

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

The pattern of the sample is as follows: