#include <iostream>
#include <cstdio>
#define INF 2000000000
using namespace std;

int mod[21][21],r[21],tr[21],p,best,lastm,lastr;

void solve(int num,int now) {
int t,i,ii,j;

	if (num>=best) return;
	if (now==0) {
		best=num;
		return;
	}
	t=mod[now][now-1];
	for (i=0;i<p;++i)
		if ((t*i)%p==r[now]) {
			for (j=1;j<now;++j) {
				tr[j]=r[j];
				r[j]=(r[j]-i*mod[j][now-1]%p+p)%p;
			}
			ii=(i==0)?0:1;
			solve(num+ii,now-1);
			for (j=1;j<now;++j)
				r[j]=tr[j];
		
		}

}			





int main() {
int n,t1,t2,i,j,k;
	while (true) {
		scanf("%d%d",&n,&p);
		if (!(p+n)) break;
		for (i=1;i<=n;++i) {
			scanf("%d",&r[i]);
			--r[i];
		}
		memset(mod,0,sizeof(mod));
		for (i=1;i<=n;++i) {
			scanf("%d",&j);
			for (;j>0;--j) {
				scanf("%d%d",&t1,&t2);
				mod[i][t1-1]=t2;
			}
			for (j=1;j<i;++j) {
				if (mod[i][j-1]==0) continue;
				t1=mod[j][j-1];
				t2=mod[i][j-1];
				r[i]=((r[i]*t1)%p-(r[j]*t2)%p+p)%p;
				for (k=j;k<n;++k) 
					mod[i][k]=((mod[i][k]*t1)%p-(mod[j][k]*t2)%p+p)%p;
			}
		}
		for (lastm=n;lastm>0;--lastm) {
			for (j=lastm-1;j<n;++j)
				if (mod[lastm][j]!=0) break;
			if (j<n) break;
		}
		for (lastr=n;lastr>0;--lastr) 
			if (r[lastr]!=0) break;	
		best=INF;
		/*for (i=1;i<=n;++i) {
			for (j=0;j<i-1;++j)
				printf("    0");
			for (j=i-1;j<n;++j)
				printf("%5d",mod[i][j]);
			printf(" =%5d\n",r[i]);
		}
		best=0;
		for (i=n;i>=1;--i) {
			t1=mod[i][i-1];
			for (j=0;j<p;++j)
				if ((t1*j)%p==r[i]) break;
			if (j==p) break;
			if ((r[i]=j)>0) ++best;
			for (j=1;j<i;++j)
				r[j]=(r[j]-r[i]*mod[j][i-1]%p+p)%p;
		}*/
		if (lastm>=lastr) 
			solve(0,n);
		if (best==INF) printf("No solution\n");
		else 
			printf("%d\n",best);
		
	}
	return 0;
}

• Re:tle (1994) dovier_antonio 2005-01-23 17:55:03
  • Re:tle (0) gigatron 2005-01-23 18:36:20