Sunny Island

One day a volcano erupted in the middle of the Pacific. After the lava cooled, a new island emerged shaped like a little sun: the land above the water formed a circle (the crater), and the lava that flowed out solidified into straight rays pointing away from the circle.

Tourists soon arrived and market stalls were set up. Stalls stand in three kinds of places.

• Around the crater rim, stalls are numbered $1$ to $n$ clockwise. Consecutively numbered stalls are neighbours, and stall $n$ neighbours stall $1$, so the rim stalls form a ring.
• Bridges are built across the crater, each resting on two rim stalls. No two bridges cross or lie above one another. The two stalls joined by a bridge are neighbours.
• Rays of solidified lava reach outward from certain rim stalls. Along a ray the stalls form a chain: the first ray stall neighbours the rim stall it starts from, and each following stall neighbours the previous one.

A local law forbids two neighbouring stalls from sharing even a single product, so neighbours must sell completely different assortments. Each stall must sell at least a given number of distinct products to stay in business (no stalls may be placed on the bridges).

Determine the smallest number of different products that must be shipped to the island so that every stall can be given at least its required number of products while no two neighbouring stalls share any product.

The first line contains the number of datasets $D$ ($1 \le D \le 20$). Each dataset is given as follows.

The first line contains $n$ ($3 \le n \le 10000$), the number of stalls on the crater rim, numbered $1$ to $n$ clockwise.

The next line contains $m$ ($0 \le m \le n-3$), the number of bridges. Each of the following $m$ lines contains two integers $p_i$ and $k_i$ ($1 \le p_i < k_i \le n$, $p_i < k_i - 1$, $k_i - p_i \ne n-1$): the rim stalls at the two ends of a bridge.

The next line contains $r$ ($0 \le r \le n$), the number of lava rays. Each of the following $r$ lines contains two integers $c_j$ and $d_j$ ($1 \le c_j \le n$, $0 \le d_j \le 10000$): the rim stall from which ray $j$ starts and the number of additional stalls on that ray.

The next line contains $n$ integers; the $i$-th is the number of distinct products the rim stall numbered $i$ must sell.

Finally there are $r$ lines; the $j$-th contains $d_j$ integers giving the required product counts of the successive stalls on ray $j$, ordered from the stall nearest the crater to the farthest.

There are at most $100000$ stalls in total, and no stall requires more than $100$ products.

For each dataset, print a single line with the minimum number of different products $t$ that must be shipped to the island so that every stall receives at least its required number of products and no two neighbouring (or bridge-joined) stalls share any product.

Figure 1. Map of the island described in the example.