题目描述

小$\red{X }$正困在一个密室里，他希望眷逃出密室。

密室中有$\red{N }$个房间，初始时，小$\red{X }$在$\red{1 }$号房间，而出口在$\red{N }$号房间。 密室的每一个房间中可能有着一些钥匙和一些传送门，一个传送门会单向地创造一条从房间$\red{X }$到房间$\red{Y }$的通道。另外，想要通过某个传送门，就必须具备一些种 类的钥匙（每种钥匙都要有才能通过）。幸运的是，钥匙在打开传送门的封印后，并不会消失。

然而，通过密室的传送门需要耗费大量的时间，因此，小$\red{X }$希望通过旧能少的传送门到达出口，你能告诉小$\red{X }$这个数值吗？

另外，小$\red{X }$有可能不能逃出这个密室，如果是这样，请输出"$\red{No Solution}$"。

输入格式

第一行三个整数$\red{N,M,K，}$分别表示房间的数量、传送门的数量以及钥匙的种类数。

接下来$\red{N }$行，每行$\red{K }$个$\red{0 }$或$\red{1，}$若第$\red{i }$个数为$\red{1，}$则表示该房间内有第$\red{i }$种钥匙，若第$\red{i }$个数为$\red{0，}$则表示该房间内没有第$\red{i }$种钥匙。

接下来$\red{M }$行，每行先读入两个整数$\red{X,Y，}$表示该传送门是建立在$\red{X }$号房间，通向$\red{Y }$号房间的，再读入$\red{K }$个$\red{0 }$或$\red{1，}$若 第$\red{i }$个数为$\red{1，}$则表示通过该传送门需要$\red{i }$种钥匙，若第$\red{i }$个数为$\red{0，}$则表示通过该传送门不需要第$\red{i }$种钥匙。

输出格式

输出一行一个"$\red{No Solution}$"，或一个整数，表示最少通过的传送门数。

样例

输入样例

3 3 2

1 0

0 1

0 0

1 3 1 1

1 2 1 0

2 3 1 1

输出样例

2

提示