时间限制：1s

空间限制：64MB

题目描述

给定一张 $n$ 个点的简单无向图。

小 A 在图上游走。他从 $1$ 号结点出发，每一步都可以沿着当前结点的某条出边移动，或者留在原地不动。

有 $m$ 个得分条件，每个条件形如 $(x,y)$，表示若小 A 经过 $x$ 步后恰好在结点 $y$，就能得一分。

小 A 想知道，他在一次游走过程中最多得多少分？

输入格式

第一行三个正整数 $n,m$。

接下来 $n$ 行，每行一个长度为 $n$ 的 01 串。第 $i$ 行第 $j$ 个字符表示 $i$ 号结点和 $j$ 号结点之间是否有边连接。

接下来 $m$ 行，每行两个正整数 $x,y$，表示一个得分条件。

输出格式

输出一行，包含一个整数，表示一次游走过程的最多得分。

样例输入 #1

5 5
00100
00110
11001
01001
00110
3 2
1 2
5 3
2 5
4 5

样例输出 #1

3

数据范围

对于所有数据，保证 $1\le n\le 500$，$1\le m\le 10^5$，$1\le x\le 10^9$，$1\le y\le n$。保证给出的图是简单无向图。

提示

请注意本题特殊的空间限制。