描述

Kid 是一名著名的盗贼，他以其独特的习惯而闻名。在每次作案前，他总会提前通知他将要抢劫的对象。尽管人们对他非常关注，但他从未失手过。这一次，Kid 告诉了一位亿万富翁 Jack，他将潜入 Jack 的家窃取他的贵重财宝。Jack 非常害怕，于是请了一位聪明的男孩 Conan 来帮助他。Conan 为 Jack 设计了一种特殊的锁。然而，Kid 非常狡猾，他偷走了锁的结构图和密码。

根据结构图（见图 1），Kid 知道这个锁包含 K 个拨盘和 K 个齿轮，每个拨盘控制若干个齿轮。每个齿轮有 N 个齿，按逆时针方向从 1 到 N 编号。当某个拨盘被拨动时，与该拨盘关联的齿轮会逆时针旋转若干个齿（不同的齿轮可能旋转不同数量的齿）。一个拨盘可以被多次拨动。在初始状态下，所有齿轮的顶部齿的数字都是 "1"。要打开锁，每个齿轮的顶部齿的数字必须是一个特定的数字。这 K 个数字构成了密码。以图 1 为例，其中 N=8, K=4；如果密码是 1-2-8-1，锁就会打开。

有了密码在手，Kid 想知道他是否能打开这把锁；如果可以，他想知道打开锁所需的最少拨动次数。你可以假设锁在开始时总是锁定的，这意味着密码不能是 K 个 "1"。

输入

输入包含多个测试用例。每个测试用例的第一行包含两个整数 K ($1 \le K \le 20$) 和 N ($2 \le N \le 10$)。接下来的一行包含 K 个整数，表示密码。密码中的每个数字都在 1 到 N 之间。然后是 K 行，第 i 行描述了第 i 个拨盘如何控制相关的齿轮。这 K 行具有以下格式：

p a1 b1 a2 b2 ... ap bp

整数 p ($0 \le p \le K$) 表示与该拨盘关联的齿轮数量。ai ($1 \le i \le p$) 是一个介于 1 和 K 之间的整数，表示第 ai 个齿轮受此拨盘控制。bi 是一个介于 1 和 N-1 之间的整数，表示当拨盘拨动一次时，第 ai 个齿轮将逆时针旋转 bi 个齿。

K = 0 且 N = 0 的测试用例表示输入结束，不应处理。

输出

对于每个测试用例，输出一行。如果锁可以打开，该行包含 Kid 所需拨动拨盘的最少次数；否则，输出 "No solution"。

样例输入

1 4
2
1 1 2
4 8
8 8 8 8
4 1 1 2 2 4 1 3 1
2 4 7 3 2
2 1 5 3 5
1 2 7
0 0

样例输出

No solution
2

来源

Beijing 2004