32163번 - 사탕 배달

문제

안즈가 전 재산을 투자해 시작한 사탕 사업이 입소문을 타고 엄청난 호황을 누리고 있다! 인건비 절약을 위해, 안즈는 공장에서 만들어진 사탕을 직접 배달하기로 한다.

안즈가 사탕을 배달해야 하는 지역은 $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)$까지 이동하여 배달을 마치기까지 소요되는 시간의 최솟값을 출력한다.

제한

힌트