C. Путешествие по музеям
ограничение по времени на тест
4 секунды
ограничение по памяти на тест
512 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

В стране $$$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$$$-й символ строки равен «1», если музей открыт в $$$j$$$-й день недели, и «0» в противном случае.

Гарантируется, для каждой пары городов $$$(u, v)$$$ существует не более одной дороги, ведущей из $$$u$$$ в $$$v$$$.

Выходные данные

Выведите одно целое число — максимальное количество различных музеев, которые можно посетить, начав путешествие в первом городе в первый день недели.

Примеры
Входные данные
4 5 3
3 1
1 2
2 4
4 1
2 3
011
110
111
001
Выходные данные
3
Входные данные
3 3 7
1 2
1 3
2 3
1111111
0000000
0111111
Выходные данные
2
Примечание
Пояснение к первому примеру

Максимально возможное количество музеев для посещения равно $$$3$$$. Можно посетить $$$3$$$ различных музея, например, так, как описано ниже.

  • День 1. Сейчас день недели $$$1$$$, и турист находится в городе $$$1$$$. Музей там закрыт. Ночью турист направляется в город $$$2$$$.
  • День 2. Сейчас день недели $$$2$$$, и турист находится в городе $$$2$$$. Музей там открыт, турист его посещает. Ночью турист направляется в город $$$4$$$.
  • День 3. Сейчас день недели $$$3$$$, и турист находится в городе $$$4$$$. Музей там открыт, турист его посещает. Ночью турист направляется в город $$$1$$$.
  • День 4. Сейчас день недели $$$1$$$, и турист находится в городе $$$1$$$. Музей там закрыт. Ночью турист направляется в город $$$2$$$.
  • День 5. Сейчас день недели $$$2$$$, и турист находится в городе $$$2$$$. Музей там открыт, но турист в нём уже был. Ночью турист направляется в город $$$3$$$.
  • День 6. Сейчас день недели $$$3$$$, и турист находится в городе $$$3$$$. Музей там открыт, турист его посещает. На этом путешествие заканчивается.
Пояснение ко второму примеру

Максимально возможное количество музеев для посещения равно $$$2$$$. Можно посетить $$$2$$$ различных музея, например, так, как описано ниже.

  • День 1. Сейчас день недели $$$1$$$, и турист находится в городе $$$1$$$. Музей там открыт, турист его посещает. Ночью направляемся в город $$$2$$$.
  • День 2. Сейчас день недели $$$2$$$, и турист находится в городе $$$2$$$. Музей там закрыт. Ночью направляемся в город $$$3$$$.
  • День 3. Сейчас день недели $$$3$$$, и турист находится в городе $$$3$$$. Музей там открыт, турист его посещает. На этом путешествие заканчивается.