Hide

Problem G
Open-Pit Mining

Open-pit mining is a surface mining technique of extracting rock or minerals from the earth by their removal from an open pit or borrow. Open-pit mines are used when deposits of commercially useful minerals or rocks are found near the surface. Automatic Computer Mining (ACM) is a company that would like to maximize its profits by open-pit mining. ACM has hired you to write a program that will determine the maximum profit it can achieve given the description of a piece of land.

Each piece of land is modelled as a set of blocks of material. Block $i$ has an associated value ($v_ i$), as well as a cost ($c_ i$), to dig that block from the land. Some blocks obstruct or bury other blocks. So for example if block $i$ is obstructed by blocks $j$ and $k$, then one must first dig up blocks $j$ and $k$ before block $i$ can be dug up. A block can be dug up when it has no other blocks obstructing it.

Input

The first line of input is an integer $N$ ($1 \leq N \leq 200$) which is the number of blocks. These blocks are numbered $1$ through $N$.

Then follow $N$ lines describing these blocks. The $i$th such line describes block $i$ and starts with two integers $v_ i$, $c_ i$ denoting the value and cost of the $i$th block ($0 \leq v_ i, c_ i \leq 200$).

Then a third integer $0 \leq m_ i \leq N-1$ on this line describes the number of blocks that block $i$ obstructs. Following that are $m_ i$ distinct space separated integers between $1$ and $N$ (but excluding $i$) denoting the label(s) of the blocks that block $i$ obstructs.

You may assume that it is possible to dig up every block for some digging order. The sum of values $m_ i$ over all blocks $i$ will be at most $500$.

Output

Output a single integer giving the maximum profit that ACM can achieve from the given piece of land.

Sample Input 1 Sample Output 1
5
0 3 2 2 3
1 3 2 4 5
4 8 1 4
5 3 0
9 2 0
2

Please log in to submit a solution to this problem

Log in