UVA11450 Wedding shopping

我们最好的朋友之一即将结婚，我们所有人都很紧张，因为他是我们中第一个结婚的人。事实上，我们从未参加过婚礼，所以没有合适的衣服或配饰。为了解决这个问题，我们决定去城里一家著名的百货商店购买所需的一切：衬衫、皮带、鞋子、领带等等。 商店为每类服装提供了不同的款式（例如，三款衬衫、两款皮带、四款鞋子……）。我们需要从每类服装中各选一款购买，且只能选一款。 由于预算有限，我们不能超支，但希望尽可能花最多的钱。可能由于资金不足，我们无法购买每类服装中的一款。

输入的第一行包含一个整数 $N$，表示测试用例的数量。每个测试用例包含若干行： - 第一行是两个整数 $M$ 和 $C$，用空格分隔 $(1 \leq M \leq 200，1 \leq C \leq 20)$，其中： - $M$ 是可用的金额。 - $C$ 是需要购买的服装种类数。 - 接下来的 $C$ 行，每行包含若干个用空格分隔的整数： - 第一个整数 $K(1 \leq K \leq 20)$ 表示该类服装的款式数量。 - 其后跟着 $K$ 个整数，表示每款服装的价格。

对于每个测试用例，输出应为一个整数，表示在不超出初始金额的情况下，购买每类服装各一款所需的最大金额。如果没有解决方案，则输出 `no solution`。