描述

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 \leq K \leq 20$）和 $N$（$2 \leq N \leq 10$）。然后是包含 $K$ 个整数的一行，表示密码。密码中的每个数字都在 1 和 $N$ 之间。然后是 $K$ 行，第 $i$ 行描述了第 $i$ 个拨号盘控制的齿轮。这 $K$ 行的格式如下：

p a1 b1 a2 b2 ... ap bp

整数 $p$（$0 \leq p \leq K$）表示受该拨号盘控制的齿轮数量。$ai$（$1 \leq i \leq p$）是一个介于 1 和 $K$ 之间的整数，表示第 $ai$ 个齿轮受该拨号盘控制。$bi$ 是一个介于 1 和 $N-1$ 之间的整数，表示当拨号盘被拨动一次时，第 $ai$ 个齿轮将旋转 $bi$ 个齿。

一个测试用例 $K = 0$ 和 $N = 0$ 表示输入结束，不应被处理。

输出

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

输入数据 1

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

输出数据 1

No solution  
2

来源

北京2004