markdown

C. 博物馆之旅

时间限制：每个测试点 $4$ 秒
内存限制：每个测试点 $512$ MB
输入：标准输入
输出：标准输出

题目描述

在这个国家中，有 $n$ 座城市，由 $m$ 条单向道路连接。尽管这个国家看似普通，但有两个有趣的事实：首先，这里的一周有 $d$ 天；其次，每座城市恰好有一座博物馆。

旅行社“开放博物馆”正在为对博物馆感兴趣的游客开发一条新路线。旅行社的员工知道每座博物馆在每周的哪些天开放。旅行必须从首都——编号为 $1$ 的城市开始，并且旅行的第一天必须是每周的第一天。每天，游客会身处某座城市，如果当天该城市的博物馆开放，则可以参观；在一天结束时，旅行要么结束，要么游客通过一条单向道路前往另一座城市。该国的道路系统设计为：每次通过道路移动需要花费一夜的时间，并且所有道路都是单向的。旅行中允许多次访问同一座城市。

你需要设计一条旅行路线，使得能够参观到的不同博物馆数量尽可能多。

输入格式

第一行包含三个整数 $n$、$m$ 和 $d$（$1 \le n \le 100000$，$1 \le m \le 100000$，$1 \le d \le 50$），分别表示城市数量、道路数量和一周的天数。

接下来的 $m$ 行，每行包含两个整数 $u_i$ 和 $v_i$（$1 \le u_i, v_i \le n$，$u_i \neq v_i$），表示一条从城市 $u_i$ 到城市 $v_i$ 的单向道路。

接下来的 $n$ 行描述了博物馆的开放时间表。第 $i$ 行对应城市 $i$ 的博物馆。每行是一个长度为 $d$ 的字符串，仅包含字符 0 或 1。如果该字符串的第 $j$ 个字符为 1，表示该博物馆在每周的第 $j$ 天开放；否则为 0。

数据保证对于任意一对城市 $(u, v)$，最多存在一条从 $u$ 到 $v$ 的道路。

输出格式

输出一个整数——从城市 $1$ 出发，在每周的第一天开始旅行，能够参观到的不同博物馆的最大数量。

样例

输入样例 1

4 5 3
3 1
1 2
2 4
4 1
2 3
011
110
111
001

输出样例 1

3

输入样例 2

3 3 7
1 2
1 3
2 3
1111111
0000000
0111111

输出样例 2

2

注释

第一个样例解释
最多可以参观 $3$ 个不同的博物馆。一种可行的路线如下：

• 第 $1$ 天：每周的第 $1$ 天，游客在城市 $1$。该博物馆关闭。当晚，游客前往城市 $3$。
• 第 $2$ 天：每周的第 $2$ 天，游客在城市 $3$。该博物馆开放，游客参观。当晚，游客前往城市 $1$。
• 第 $3$ 天：每周的第 $3$ 天，游客在城市 $1$。该博物馆开放，游客参观。当晚，游客前往城市 $2$。
• 第 $4$ 天：每周的第 $1$ 天，游客在城市 $2$。该博物馆关闭。当晚，游客前往城市 $4$。
• 第 $5$ 天：每周的第 $2$ 天，游客在城市 $4$。该博物馆开放，但游客已经参观过。当晚，游客前往城市 $1$。
• 第 $6$ 天：每周的第 $3$ 天，游客在城市 $1$。该博物馆开放，游客参观。之后旅行结束。

第二个样例解释
最多可以参观 $2$ 个不同的博物馆。一种可行的路线如下：

• 第 $1$ 天：每周的第 $1$ 天，游客在城市 $1$。该博物馆开放，游客参观。当晚，游客前往城市 $2$。
• 第 $2$ 天：每周的第 $2$ 天，游客在城市 $2$。该博物馆关闭。当晚，游客前往城市 $3$。
• 第 $3$ 天：每周的第 $3$ 天，游客在城市 $3$。该博物馆开放，游客参观。之后旅行结束。