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.