Although five 3 cent stamps yields an envelope with 15 cents postage, it is not possible to cover an
envelope with 14 cents of stamps using at most five 1 and 3 cent stamps. Since the postal service wants
maximal coverage without gaps, the maximal coverage is 13 cents.
The first line of each data set contains the integer S, representing the maximum of stamps that an
envelope can accommodate. The second line contains the integer N , representing the number of sets of
stamp denominations in the data set. Each of the next N lines contains a set of stamp denominations.
The first integer on each line is the number of denominations in the set, followed by a list of stamp
denominations, in order from smallest to largest, with each denomination separated from the others by
one or more spaces. There will be at most S denominations on each of the N lines. The maximum
value of S is 10, the largest stamp denomination is 100, the maximum value of N is 10.
If more than one set of denominations in a set yields the same maximal no-gap coverage, the set
with the fewest number of denominations should be printed (this saves on stamp printing costs). If two sets with the same number of denominations yield the same maximal no-gap coverage, then the
set with the lower maximum stamp denomination should be printed. For example, if five stamps fit on
an envelope, then stamp sets of 1, 4, 12, 21 and 1, 5, 12, 28 both yield maximal no-gap coverage of 71
cents. The first set would be printed because both sets have the same number of denominations but
the first set’s largest denomination (21) is lower than that of the second set (28). If multiple sets in a
sequence yield the same maximal no-gap coverage, have the same number of denominations, and have
equal largest denominations, then print the set with the lewer second-maximum stamp denomination,
and so on.
