Maximum Reward for Assembling Toys

In this problem, you are given the number of different parts and the number of toy types. You also have a list of available parts and a list of toy requirements. Each toy is described by a reward value and the amount of each part required to assemble it. A toy can be assembled if, for every part, the available parts are not less than the corresponding requirement. The process is iterative: while you can assemble at least one toy, choose the one with the highest reward (if more than one exists, choose any among them) and assemble it exactly once, reducing the available parts accordingly. The goal is to maximize the total reward. If no toy can be assembled even once, output (-1).

Formally, let (P) be the number of part types and (T) be the number of toys. You are given a vector (q = [q_1, q_2, \dots, q_P]) representing the available quantities of parts. Each toy is given by a list ([r, a_1, a_2, \dots, a_P]), where (r) is the reward for assembling that toy and (a_i) is the number of the (i)th part required. Assemble the toys repeatedly in a greedy fashion until no further toy can be assembled, and output the accumulated reward (or (-1) if no toy was assembled).

inputFormat

The input is given from standard input (stdin) in the following format:

Line 1: Two integers, (P) (the number of parts) and (T) (the number of types of toys). Line 2: (P) integers representing the available quantity for each part. The next (T) lines: Each line contains (P+1) integers. The first integer is the reward for the toy, followed by (P) integers specifying the quantity required for each part.

outputFormat

Output a single integer, which is the maximum total reward obtainable. If no toy can be assembled even once, output (-1). The output should be written to standard output (stdout).## sample

3 2
10 5 7
8 2 1 3
5 1 2 2

16