Craftsman
Time limit8sMemory limit512 MB
Choose which orders to accept and which tools to buy, where discounted tool pairs bought together change the cost, to maximize income minus tool cost.
- Level
Hard8 of 10
- Topics
- Dynamic programming, Bit manipulation, Graph, Combinatorics
- Solved
- No attempts yet
Problem
Takeshi is a famous craftsman who receives many offers from all over Japan. The tools he uses now have become too old. He plans to buy new tools and replace the old ones before he next uses the tools. Some offers may cost him money if the offer requires the tools to be replaced. So accepting every order he has received is not necessarily best. You are one of his disciples. Your task is to compute, for a given list of orders and tool prices, the set of orders to accept that maximizes his earning. His earning can go up or down because of sale income and replacement cost.
He always buys tools from his friend's shop. The shop discounts the prices of some pairs of items when the pair is bought at the same time. You have to account for the discount. The total price to pay may differ from the simple sum of the individual prices.
You may assume that all the tools at the shop are tough enough. Takeshi can complete every order with the tools he replaces this time. So you have to buy at most one tool of each kind.
Input
The input conforms to the following format:
N M P
X1 K1 I1,1 ... I1, K1
...
XN KN IN,1 ... IN, KN
Y1
...
YM
J1,1 J1,2 D1
...
JP,1 JP,2 DP
Here N, M, P are the numbers of orders, tools sold in the shop, and pairs of discountable items, respectively.
The following N lines specify the details of the orders. Xi is an integer giving the compensation for the i-th order, and Ki is the number of tools required to complete the order. The remaining part of each line describes the tools required to complete the order. Tools are specified by integers from 1 through M.
The next M lines are the price list at the shop of Takeshi's friend. An integer Yi gives the price of the i-th tool.
The last P lines of each test case give the pairs of items to be discounted. When Takeshi buys the Ji,1-th and the Ji,2-th tool at the same time, he has to pay only Di yen instead of the sum of their individual prices. No tool appears more than once in the discount list, and max{Yi, Yj} < Di,j < Yi + Yj holds for every discount price, where Di,j is the discount price of the i-th and j-th tools bought at the same time.
It is also guaranteed that 1 ≤ N ≤ 100, 2 ≤ M ≤ 100, 1 ≤ Ki ≤ 100, 1 ≤ P ≤ M/2, and 1 ≤ Xi, Yi ≤ 1000.
Output
Output the maximum possible earning of Takeshi to standard output.