K. A Potion Shopping On This Wonderful World!
time limit per test
1 second
memory limit per test
256 megabytes
input
standard input
output
standard output

In another world, aside from luck, there are $$$K$$$ types of stat for each adventurer.

In that world, there is a shop run by an archwizard lady and a masked man. The shop is likely going to go bankrupt in the near future because the archwizard always purchases useless stuff as an investment. However, she is certain that the investment this time will surely return profit, with buff potions!

The shop plans to sell $$$N$$$ kinds of potions. The $$$i^{th}$$$ kind potion buffs $$$n_i$$$ types of stat: $$$t_1,t_2,\dots,t_{n_i}$$$ and costs $$$c_i$$$ units. When the $$$i^{th}$$$ kind potion is consumed, if the consumer is lucky, each stat type of all $$$n_i$$$ types will be maximized, or else, if they are not lucky enough, the consumer will not get any buff and will have diarrhea instead. The effect lasts one day for both cases. Different kinds of potions can be consumed together. The shop stocks each kind of potion abundantly such that it is guaranteed that there is no kind of potion that will run out of stock.

A certain adventurer with extreme luck makes a plan to buy potions because he suffers too much headache from his party in each and every mission. "Last mission, my archpriest's healing almost killed me. My archwizard blows up everything — including the money from the mission. And my crusader...she was too busy enjoying the pain." — he facepalms while writing the plan.

With his luck, he knows that every potion he consumes will definitely be effective. There are currently $$$M$$$ days in his plan. On the $$$i^{th}$$$ day, he wants to maximize $$$m_i$$$ types of stat: $$$w_1,w_2,\dots,w_{m_i}$$$. He doesn't care if the potions buff other stat types that are not listed. He wants to know the minimum cost of potions he needs to buy to achieve that goal.

Input

The first line contains three integers $$$N$$$, $$$M$$$, and $$$K(1 \leq N,\ M \leq 2 \cdot 10^4,\ 1 \leq K \leq 14)$$$ — the number of kinds of potion, the number of planned days, and the number of types of stat, respectively.

The following $$$2N$$$ lines describe potion kind $$$1,2,\dots,N$$$ respectively. Each kind of potion is described by two lines.

The first line contains two integers $$$n$$$ and $$$c(1 \leq n \leq K, 1 \leq c \leq 10^5)$$$ — the number of stat types the potion buffs, and the cost of the potion respectively.

The second line contains $$$n$$$ integers $$$t_1,t_2,\dots,t_n(1 \leq t_1 \lt t_2 \lt \dots \lt t_n \leq K)$$$ — the types of stat buffed.

The following $$$2M$$$ lines describe plans in $$$M$$$ days. A plan in each day is described by two lines.

The first line contains one integer $$$m(1 \leq m \leq K)$$$ — the number of stat types required that day.

The second line contains $$$m$$$ integers $$$w_1,w_2,\dots,w_m(1 \leq w_1 \lt w_2 \lt \dots \lt w_m \leq K)$$$ — the types of stat required that day.

Output

Output $$$M$$$ lines – the cost for each day from day $$$1$$$ to $$$M$$$.

Each line, output $$$-1$$$ if that day the adventurer cannot maximize all the required types, else output the minimum cost he needs for that day.

Examples
Input
3 3 3
2 4
1 2
2 4
2 3
3 9
1 2 3
1
1
1
3
3
1 2 3
Output
4
4
8
Input
3 1 3
2 4
1 2
2 4
2 3
3 7
1 2 3
3
1 2 3
Output
7
Input
1 1 2
1 2
1
1
2
Output
-1
Note

In example $$$1$$$, for the first day, he can buy the first kind for stat type $$$1$$$ and $$$2$$$, which cover his requirement (type 1).

For the third plan, he can buy the first and second kind which, together, cover stat type $$$1$$$, $$$2$$$, and $$$3$$$ for $$$8$$$ units. It is cheaper than buying the third kind, which also covers the requirement.

In example $$$3$$$, there is no potion which buffs stat type $$$2$$$.