연료가 부족해

피라미드를 직접 보는 것이 소원이었던 향빈이는 사막 투어 여행패키지를 신청했다. 여행 둘째 날, 사막 입구에 도착한 향빈이는 사막 투어용 자동차에 탑승했다.

출발을 기다리며 자동차 안에 앉아 있던 향빈이는 사막 투어 가이드북을 발견했다. 가이드북 안의 $R \times C$ 크기 지도에는 연료 보관소 $N$곳의 위치와 연료 보관소마다 보관 중인 연료량이 표시되어 있었다.

자동차 덕후였던 향빈이는 모든 자동차의 연비를 외우고 있었고, 지금 탑승한 자동차가 거리 $1$만큼 움직일 때 연료를 $1$만큼 소비한다는 것을 알고 있다. 자동차는 지도의 $x$축 또는 $y$축과 평행한 방향으로만 주행한다. 예를 들어 자동차가 $\left(0,0\right)$에서 $\left(i,j\right)$까지 최단 거리로 움직이면 연료는 $i+j$만큼 소비된다.

현재 자동차에는 연료가 없어서, 향빈이는 여기 있는 주유소에서 연료를 충전한 뒤 출발하려 한다. 하지만 주유소에서 파는 연료는 매우 비싸기 때문에, 향빈이는 여기서는 연료를 최소한으로 충전하고 이후에는 이동하면서 방문하는 연료 보관소에서 연료를 충전할 계획이다.

향빈이는 얼른 피라미드를 보고 싶어서 운전사에게 피라미드와 멀어지는 방향으로는 운전하지 말아 달라고 부탁했다. 즉, 자동차는 오른쪽이나 아래쪽으로만 이동한다.

주유소에서 충전할 수 있는 연료량에는 제한이 없고, 현재 위치와 피라미드가 있는 위치에는 연료 보관소가 없다. 또한 한 위치에 연료 보관소가 두 곳 이상 있는 경우는 없다.

연료 보관소마다 위치와 보관된 연료량이 다르기 때문에, 어떤 순서로 연료 보관소를 경유하는지에 따라 처음 충전해야 하는 연료량이 달라질 수 있다. 현재 위치인 $\left(1,1\right)$에서 피라미드가 있는 $\left(R,C\right)$까지 가기 위해 주유소에서 충전해야 하는 연료량의 최솟값을 구해 보자.

첫째 줄에 지도의 세로 길이와 가로 길이를 나타내는 정수 $R$, $C$가 주어진다. ($2 \leq R, C \leq 3\ 000$)

둘째 줄에 지도에 표시된 연료 보관소의 개수를 나타내는 정수 $N$이 주어진다. ($0 \leq N \leq 1\ 000$)

셋째 줄부터 $N$개 줄에 각 연료 보관소의 위치를 나타내는 정수 좌표 $\left(r,c\right)$와 보관 중인 연료량을 나타내는 정수 $f$가 주어진다. ($1 \leq r \leq R$, $1 \leq c \leq C$, $0 \leq f \leq 100$)

향빈이가 현재 위치인 $\left(1,1\right)$에서 피라미드가 있는 $\left(R,C\right)$까지 가기 위해 주유소에서 충전해야 하는 연료량의 최솟값을 출력한다.