You take part in robotechnical contest "RoboFest". Your robot must pass all intermediate checkpoints and return to start. You have the map of the area, and you want to find optimal route for your robot. The map is a matrix with \textbf{N}×\textbf{M} cells. Robot can move from cell to another cell if the cells have common side. Each cell has an integer number - the time robot will take to arrive to this cell (to get to this cell from a neighbor one). Also you have the list of coordinates of intermediate checkpoints and of the start/finish. You can pass the checkpoints in any order. \InputFile First line contains integer numbers \textbf{N} and \textbf{M} (\textbf{1} ≤ \textbf{N}, \textbf{M} ≤ \textbf{40}). Next \textbf{N} lines contain \textbf{M} integer numbers each, separated by spaces - the time values, required to arrive to the corresponding cells. Next line contains \textbf{K} - the quantity of intermediate checkpoints (\textbf{1} ≤ \textbf{K} ≤ \textbf{15}). Next \textbf{K} lines contain two integer numbers each (\textbf{X_i} and \textbf{Y_i}), separated by spaces - the coordinates of corresponding checkpoints (\textbf{0} ≤ \textbf{X_i} < \textbf{N}, \textbf{0} ≤ \textbf{Y_i} < \textbf{M}). Next line contains two integer numbers (\textbf{X} and \textbf{Y}), separated by spaces - the coordinates of the start/finish (\textbf{0} ≤ \textbf{X} < \textbf{N}, \textbf{0} ≤ \textbf{Y} < \textbf{M}). \textbf{X}-coordinates are zero-indexed rows, numerated from up to down. Y-coordinates are zero-indexed columns, numerated from left to right. \OutputFile Output the minimal time, robot will take to finish the race.