사탕 배달

안즈가 전 재산을 투자해 시작한 사탕 사업이 입소문을 타고 큰 호황을 누리고 있다! 인건비를 아끼려고, 안즈는 공장에서 만든 사탕을 직접 배달하기로 한다.

사탕을 배달하는 지역은 $N \times M$ 크기의 격자이다. 격자의 $x$행 $y$열에 있는 칸을 $(x, y)$라고 하자.

한 번의 배달은 $(1, 1)$에서 출발해 $(N, M)$에서 끝나야 한다. 이 지역의 도로는 모두 일방통행이라서, 배달할 때는 아래쪽이나 오른쪽으로만 이동해야 한다. 즉, $(x, y)$에 있다면 $(x+1, y)$나 $(x, y+1)$로만 이동할 수 있다. $(x, y)$에서 다른 칸으로 이동하는 데는 $C\_{x,y}$의 시간이 걸린다.

안즈는 총 $K$개의 집에 사탕을 배달해야 한다. 안즈가 집이 있는 칸으로 이동하면, 그 집의 배달은 끝난 것이다. 한 번의 배달로 모든 집을 들르지 못할 수도 있으므로, 배달은 여러 번 진행할 수 있다. 다시 배달을 시작하려면 $(N, M)$에서 $(1, 1)$로 돌아와야 하며, 이 이동에는 $C\_{N,M}$의 시간이 걸린다. 배달은 원하는 만큼 진행할 수 있으며, 배달 횟수를 최소화할 필요는 없다.

안즈는 모든 집에 사탕 배달을 마친 뒤 $(N, M)$까지 이동해 배달을 끝내려고 한다. 이때 걸리는 시간을 알고 싶지만, 직접 계산하기에는 너무 번거로워 여러분에게 해결을 부탁했다.

첫 번째 줄에 $N$, $M$, $K$가 공백으로 구분되어 주어진다. ($3 \le N,M \le 500$; $1 \le K \le \min(100, NM - 2)$)

이어서 $N$개의 줄에 걸쳐 수 $M$개가 공백으로 구분되어 주어진다. $i$번째 줄의 $j$번째 수는 $C\_{i,j}$이다. ($1 \le C\_{i,j} \le 1\,000\,000\,000$)

이어서 $K$개의 줄에 걸쳐 $i$번째 집의 위치 $(x_i, y_i)$가 공백으로 구분되어 주어진다. 모든 집의 위치는 서로 다르며, $(1, 1)$이나 $(N, M)$에는 집이 없다. ($1 \le x_i \le N$; $1 \le y_i \le M$)

안즈가 모든 집에 사탕 배달을 마친 뒤 $(N, M)$까지 이동해 배달을 끝내기까지 걸리는 시간의 최솟값을 출력한다.