PKU205 Kid

Kid 是一位著名的怪盗，他有一个独特的习惯：每次行动前，都会提前通知即将被盗的人。尽管人们严加防范，他却从未失手。

这一次，Kid 通知富翁 Jack，自己将进入他的家中取走昂贵的宝物。Jack 十分害怕，于是请聪明的少年 Conan 帮忙。Conan 为 Jack 的住宅设计了一把特殊的锁。然而，狡猾的 Kid 偷到了这把锁的结构图和密码。

这把锁包含 $K$ 个旋钮和 $K$ 个齿轮，每个旋钮控制若干个齿轮。每个齿轮上有 $N$ 个齿，按逆时针方向依次编号为 $1$ 到 $N$ 。每次拨动一个旋钮时，受该旋钮控制的齿轮都会逆时针转过若干个齿，不同齿轮转过的齿数可能不同。每个旋钮均可拨动多次。

初始时，所有齿轮位于最上方的齿编号均为 $1$ 。要打开锁，每个齿轮位于最上方的齿都必须达到指定编号，这 $K$ 个编号共同组成密码。例如，当 $N=8$ 、 $K=4$ ，密码为 $(1,2,8,1)$ 时，只要各齿轮顶部的编号依次为这些值，锁就会打开。

Kid 想知道自己能否打开这把锁。如果可以，请求出打开锁所需的最少旋钮拨动次数。可以保证锁在初始状态下不会直接打开，即密码不可能全部由 $1$ 组成。

输入格式

输入包含多组测试数据。

每组测试数据的第一行包含两个整数 $K$ 和 $N$ ，分别表示旋钮与齿轮的数量，以及每个齿轮的齿数。

第二行包含 $K$ 个整数，表示锁的密码。

接下来 $K$ 行，第 $i$ 行描述第 $i$ 个旋钮所控制的齿轮，格式如下：

p\ a_1\ b_1\ a_2\ b_2\ \cdots\ a_p\ b_p

其中， $p$ 表示该旋钮控制的齿轮数量。对于每个满足 $1\le i\le p$ 的 $i$ ， $a_i$ 表示该旋钮控制第 $a_i$ 个齿轮， $b_i$ 表示每拨动一次该旋钮，第 $a_i$ 个齿轮将逆时针转过 $b_i$ 个齿。

当读入 $K=0$ 且 $N=0$ 时，表示输入结束，该组数据无须处理。

对于每组测试数据输出一行。

如果可以打开锁，输出所需的最少旋钮拨动次数；否则输出 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

本题题面与测试数据整理自 BZOJ。

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