Max Distinct Markets

You are given a transportation network of n cities connected by m bidirectional railway tracks, and a weekly schedule of market days over d days. Each city has a string of length d describing when a market is held (with '1' indicating a market day). Starting from city 1 on day 0 (the first day of the week), you may travel along the railway tracks. Every time you reach a city, if that city has a market on the current day, you can visit it. Your task is to determine the maximum number of distinct markets you can visit during your journey.

Note: On each move to an adjacent city, the day advances by one (cyclically modulo d). A city’s market is counted only once, even if visited on multiple days.

The relation between the parameters can be summarized by the following:

\( \text{result} = \max\{\text{number of distinct markets visited}\} \)

inputFormat

The input is read from stdin and has the following format:

n m d
u1 v1
u2 v2
... (m lines representing the tracks)
market_day_string_1
market_day_string_2
... (n lines, each a string of length d)

Where:

• n: Number of cities.
• m: Number of railway tracks.
• d: Number of days in a week.
• Each of the next m lines contains two integers u and v indicating a bidirectional track between cities u and v.
• Each of the next n lines is a string representing the market schedule for a city (where '1' means a market is held on that day and '0' means it is not).

outputFormat

Output to stdout a single integer denoting the maximum number of distinct markets that can be visited.

## sample

5 5 7
1 2
1 3
2 4
3 5
4 5
1010101
0101010
1110000
0001111
1000001

4