Hyundai Mobis Autonomous Driving System

At the Seosan test track of Hyundai Mobis, a mobility fitted with parts from the company's new autonomous driving system is undergoing driving tests. The system uses satellite imagery to recognize the area around the mobility and computes the shortest distance from its current position to the destination. The old system moved the mobility only up, down, left, and right. The new system moves it in those four directions and also with additional movement patterns. The system cannot keep communicating with the satellite, so the additional patterns cannot be used without limit.

Seungjun is testing this system to find the shortest distance from a fixed start at the top-left corner to a fixed final destination at the bottom-right corner, passing through at least one of the waypoints. The destination may itself be a waypoint, in which case visiting the waypoint counts as arriving at the destination. Given the map, the additional movement patterns, and the number of times each pattern may be used, write a program that finds the shortest distance from the start, through at least one waypoint, to the final destination.

A pattern is given as a $5 \times 5$ array. The mobility is at row $3$, column $3$ of the array. If the value at row $A$, column $B$ is $1$, the system can use a pattern that moves the mobility from row $3$, column $3$ to row $A$, column $B$.

The first line contains the height $N$, the width $M$, and the number of pattern uses $K$. $(1 \leq N,M \leq 200, 0 \leq K \leq 30)$

The map has $N$ rows and $M$ columns. 0 is an empty cell, 1 is a wall, and 2 is a waypoint. The mobility cannot move onto a wall or outside the map. The start at the top-left cell is guaranteed to be 0.

The next 5 lines give the $5 \times 5$ pattern array, with values 0 or 1.

Print the shortest distance from the start, passing through at least one waypoint, to the destination. If the destination cannot be reached through at least one waypoint in any case, print -1.