该比赛已结束，您无法在比赛模式下递交该题目。您可以点击“在题库中打开”以普通模式查看和递交本题。

Description

小 C 正困在一个密室里，他希望尽快逃出密室。
密室中有N个房间，初始时，小 C 在1号房间，而出口在N号房间。
密室的每一个房间中可能有着一些钥匙和一些传送门，一个传送门会单向地创造一条从房间X到房间Y的通道。另外，想要通过某个传送门，就必须具备一些种类的钥匙（每种钥匙都要有才能通过）。幸运的是，钥匙在打开传送门的封印后，并不会消失。
然而，通过密室的传送门需要耗费大量的时间，因此，小 C希望通过尽可能少的传送门到达出口，你能告诉小C这个数值吗？
另外，小C有可能不能逃出这个密室，如果是这样，
请输出 "No Solution"。

Format

Input

第一行三个整数 N,M,K，分别表示房间的数量、传送门的数量以及钥匙的种类数。
接下来N行，每行K个0或1，若第i个数为1，则表示该房间内有第 i 种钥匙，若第i个数为0，则表示该房间内没有第i种钥匙。
接下来M行，每行先读入两个整数X,Y，表示该传送门是建立在X号房间，通向Y号房间的，再读入K个0或1，若第i个数为1，则表示通过该传送门需要i种钥匙，若第i个数为0，则表示通过该传送门不需要第i种钥匙。

Output

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

Sample 1

Input

3 3 2
1 0
0 1
0 0
1 3 1 1
1 2 1 0
2 3 1 1

Output

2

Limitation

0.5s, 262144KiB for each test case.

Hint

Source

高一年级信息学奥赛模拟考(一)（第二学期）