15273번 - 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.

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

Then follow N lines describing these blocks. The ith such line describes block i and starts with two integers v_i, c_i denoting the value and cost of the ith block (0 ≤ v_i , c_i ≤ 200)

Then a third integer 0 ≤ m_i ≤ 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 a single integer giving the maximum profit that ACM can achieve from the given piece of land.