Hardware Store (hardware.X)
The mall has a hardware store! The cows are ecstatic as their head
fills with visions of all the fabulous projects they can build. The
hardware store sells T (1 <= T <= 1000) different kinds of tools
conveniently numbered 1..T, each of which has some integer price
(range: 1..10,000).
The cows have a list of P (1 <= P <= 1000) projects that they are
contemplating building. Each project has an intrinsic integer 'value'
(range: 1..10,000) upon completion and a list of tools it requires.
The total number of requirement (tool, project) pairs is at most
10,000.
The cows want to know how to maximize their apparent profit (which
is calculated as the sum of the values of all the completed projects
minus the sum of the cost of all the tools). The cows will only buy
a tool once and can, if they wish, use it for multiple projects.
What is the maximum profit the cows can make?
PROBLEM NAME: hardware
INPUT FORMAT:
* Line 1: Two space-separated integers: T and P
* Lines 2..T+1: Line i+1 a single integer that is the price of tool i
* Lines T+2..T+P+1: Each line contains several space-separated
integers that describe a project that can be built. The first
integer is the value of the project upon completion. The
second integer is the number of tools required, N. The next N
integers are unique and compose the list of required tools.
SAMPLE INPUT:
4 3
2
3
4
5
3 2 1 2
4 3 1 3 4
7 2 2 3
OUTPUT FORMAT:
* Line 1: A single integer that is the maximum profit that cows can
make.
SAMPLE OUTPUT:
1
EXPLANATION:
The cows buy tools 1, 2, and 3 and they complete projects #1 and #3. The cost is 9 and the profit is 10.