在 $$$N$$$ 国家,有 $$$n$$$ 个城市由 $$$m$$$ 单向道路连接。虽然这个国家看起来不起眼,但有两个有趣的事实。起初,这里一周持续 $$$d$$$ 天。其次,该国每个城市只有一个博物馆$$$N$$$。
旅行社“开放博物馆”正在为对博物馆感兴趣的游客开发一项新计划。该机构的员工知道每个博物馆的开放日期。游览应从首都开始 - 城市编号 $$$1$$$,并且游览的第一天必须是一周的第一天。每天,游客都会在某个城市,在其博物馆观看博览会(如果博物馆今天开放),到一天结束时,旅行要么结束,要么游客进入另一个城市,通过一条道路与当前城市相连。 $$$N$$$的道路系统的设计方式是,通过一条道路行驶总是需要一晚,而且所有道路都是单向的。旅行期间允许多次访问一个城市。
您应该为旅行制定这样的路线,即在旅行期间可以参观的不同博物馆的数量最多。
输入
第一行包含三个整数 $$$n$$$、$$$m$$$ 和 $$$d$$$ ($$$1 \leq n \leq 100\,000$$$, $$$0 \leq m \leq 100\,000$$$, $$$1 \leq d \leq 50$$$),城市数量,数量道路的数量和一周的天数。
接下来的 $$$m$$$ 行包含两个整数 $$$u_i$$$ 和 $$$v_i$$$ ($$$1 \le u_i, v_i \le n$$$, $$$u_i \ne v_i$$$),表示从城市 $$$u_i$$$ 到城市 $$$v_i$$$ 的单向道路。
接下来的 $$$n$$$ 行包含博物馆的时间表。位于第 $$$i$$$ 城市的博物馆的时间表在这些行的第 $$$i$$$ 中描述。每行恰好由 $$$d$$$ 个字符“0”或“1”组成,如果博物馆在一周的第 $$$j$$$ 开放,则字符串的第 $$$j$$$ 个字符等于“1”,否则等于“0”。
保证对于每对城市 $$$(u, v)$$$ ,从 $$$u$$$ 到 $$$v$$$ 的道路不超过一条。
输出
打印一个整数 - 在一周的第一天在第一个城市开始旅行时可以参观的不同博物馆的最大数量。
示例
输入 #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$$$。例如,可以按照下面描述的方式参观 $$$3$$$ 博物馆。
- 第 1 天。现在是一周的第一天,游客在城市 $$$1$$$。那里的博物馆关门了。晚上,游客前往城市编号$$$2$$$。
- 第 2 天。现在是一周的第二天,游客在城市中 $$$2$$$。那里的博物馆开放了,游客参观。晚上,游客前往城市编号$$$4$$$。
- 第三天。现在是一周的第三天,游客在城市中 $$$4$$$。那里的博物馆开放了,游客参观。晚上,游客前往城市编号$$$1$$$。
- 第 4 天。现在是一周的第一天,游客在城市中 $$$1$$$。那里的博物馆关门了。晚上,游客前往城市编号$$$2$$$。
- 第 5 天。现在是一周的第 2 天,数字 $$$2$$$,游客在城市 $$$2$$$。那里的博物馆开放了,但是游客已经参观过了。晚上,游客前往城市编号$$$3$$$。
- 第 6 天。现在是一周的第三天,游客在城市中 $$$3$$$。那里的博物馆开放了,游客参观。在此之后,游览就结束了。
第二个例子的解释
参观的不同博物馆的最大数量为 $$$2$$$。例如,可以按照下面描述的方式参观 $$$2$$$ 博物馆。
- 第 1 天。现在是一周的第一天,游客在城市中 $$$1$$$。那里的博物馆开放了,游客参观。晚上,游客前往城市编号$$$2$$$。
- 第 2 天。现在是一周的第二天,游客在城市中 $$$2$$$。那里的博物馆关门了。晚上,游客前往城市编号$$$3$$$。
- 第三天。现在是一周的第三天,游客在城市中 $$$3$$$。那里的博物馆开放了,游客参观。在此之后,游览就结束了。