J. Jumping Through Hyperspace
time limit per test
2 seconds
memory limit per test
256 megabytes
input
standard input
output
standard output

Year $$$2333$$$. After the discovery of Hyperspace, interplanetary travel has become a commonplace activity. By this time, humanity has already colonized $$$n$$$ distinct planets. Each planet has a hyperport that facilitates travel to other planets using hyperjumps.

Due to the peculiarities of spacetime fabric, the duration of a hyperjump is not constant. It depends on the time the journey begins and the type of hyperjump. Specifically, for hyperjump type $$$i$$$ and start time $$$s_i$$$, the total travel time is given by the equation $$$T = ((a_is_i + b_i) \bmod c_i) + d_i$$$, where $$$a_i$$$, $$$b_i$$$, $$$c_i$$$, and $$$d_i$$$ are parameters corresponding to the $$$i$$$-th type of hyperjump.

You start on planet number $$$1$$$ and wish to reach planet number $$$n$$$. What is the minimum amount of time it will take to accomplish this?

Input

The first line contains the integers $$$n$$$, $$$m$$$, and $$$s$$$ — the number of planets, the number of hyperjump types, and the current time ($$$2 \le n \le 2000$$$, $$$1 \le m \le 50$$$, $$$1 \le s \le 2\,000$$$).

The next $$$m$$$ lines consist of the $$$i$$$-th line containing the character $$$z_i$$$ — the identifier of the $$$i$$$-th hyperjump type (a lowercase or uppercase Latin letter), followed by the integers $$$a_i$$$, $$$b_i$$$, $$$c_i$$$, and $$$d_i$$$ — the parameters of the hyperjump of type $$$i$$$ ($$$1 \le a_i, b_i, c_i, d_i \le 2\,000$$$). The hyperjump identifiers are unique.

Each of the subsequent $$$n$$$ lines contains $$$n$$$ characters. The $$$j$$$-th character in the $$$i$$$-th line corresponds to the hyperjump type that allows moving from planet $$$i$$$ to planet $$$j$$$. If no hyperjump is available from planet $$$i$$$ to planet $$$j$$$, the character will be ".".

Output

Output a single integer — the minimum time required to travel from planet number $$$1$$$ to planet number $$$n$$$.

If it is impossible to reach planet $$$n$$$ from planet $$$1$$$ using a sequence of one or more hyperjumps, output $$$-1$$$.

Example
Input
3 2 1
A 1 1 5 1
a 2 2 7 1
.A.
..a
a..
Output
6
Note

Explanation for the example: the cheapest way to jump from planet $$$1$$$ to planet $$$2$$$ is to jump at time $$$1$$$ and arrive at time $$$4$$$; when jumping from planet $$$2$$$ to planet $$$3$$$, it is optimal to wait for two time units, execute the jump in one time unit, and arrive at time $$$7$$$.