描述

集邮者早在邮政员工产生不满情绪之前就开始收集邮票了。邮票过剩对一个国家的邮政服务而言或许是坏消息，但对收集过剩邮票的人来说却是好消息。邮政服务致力于将提供无缝邮资覆盖所需的邮票数量降至最低。为此，你被要求编写一个程序来协助邮政服务。

信封尺寸限制了一个信封上所能使用的邮票数量。例如，若有1美分和3美分的邮票可用，且一个信封可容纳5枚邮票，那么从1美分到13美分的所有邮资都能被"覆盖"：

 邮费   1¢ 邮票数目	3¢ 邮票数目

  1         1           0

  2         2           0

  3         0           1

  4         1           1

  5         2           1

  6         0           2

  7         1           2

  8         2           2

  9         0           3

  10        1           3

  11        2           3

  12        0           4

  13        1           4

虽然五枚3美分的邮票可以组成15美分的邮资，但无法用最多五枚1美分和3美分的邮票组合出14美分的邮资。由于邮政服务希望实现无间隙的最大覆盖，因此最大覆盖值为13美分。

输入

每个数据集的第一行包含整数$S$，表示一个信封最多可容纳的邮票数量。第二行包含整数$N$，表示数据集中邮票面值集合的数量。接下来的$N$行每行包含一组邮票面值。每行的第一个整数是该组面值的数量，后跟按从小到大顺序排列的邮票面值列表，每个面值之间用一个或多个空格分隔。$N$行中每行最多有$S$个面值。$S$的最大值为10，最大邮票面值为100，$N$的最大值为10。

输入以一个以零开头的数据集（$S$为零）结束。

输出

对于每个数据集，输出一行，给出最大无间隙覆盖值，后跟产生该覆盖的邮票面值，格式如下：

最大覆盖值 = <值> : <面值>

如果数据集中有多个面值集合产生相同的最大无间隙覆盖，则应打印面值数量最少的集合（这可以节省邮票印刷成本）。如果两个具有相同面值数量的集合产生相同的最大无间隙覆盖，则应打印最大邮票面值较小的集合。例如，如果一个信封最多可容纳五枚邮票，那么面值集合1, 4, 12, 21和1, 5, 12, 28都能产生71美分的最大无间隙覆盖。应打印第一个集合，因为两个集合的面值数量相同，但第一个集合的最大面值（21）小于第二个集合的最大面值（28）。如果序列中有多个集合产生相同的最大无间隙覆盖、具有相同的面值数量且最大面值相等，则应打印其中的第一个集合。

输入数据 1

5
2
4 1 4 12 21
4 1 5 12 28
10
2
5 1 7 16 31 88
5 1 15 52 67 99
6
2
3 1 5 8
4 1 5 7 8
0

输出数据 1

max coverage = 71 : 1 4 12 21
max coverage = 409 : 1 7 16 31 88
max coverage = 48 : 1 5 7 8