선반

경찰서의 물품 보관대는 $C$개의 열(column)과 $R$개의 행(row)으로 이루어진 선반들로 구성되어 있다.

선반 위의 물건을 꺼내려면 사다리를 사용해야 한다. 사다리는 하나의 열에만 기대어 세울 수 있다. 어떤 열에 사다리를 세우고 특정 높이(행)까지 올라가면, 그 열은 물론 바로 양옆(왼쪽과 오른쪽)에 붙어 있는 열에서도 올라간 높이 이하에 놓인 모든 물건을 꺼낼 수 있다.

즉, $c$번 열에 사다리를 세워 높이 $h$까지 올라가면 $c-1$, $c$, $c+1$번 열의 $1$번 행부터 $h$번 행까지에 놓인 물건을 모두 꺼낼 수 있다. (맨 왼쪽 열의 왼쪽이나 맨 오른쪽 열의 오른쪽에는 열이 존재하지 않는다.)

경찰들은 보관대에서 필요한 물건들을 꺼내야 한다. 작업 중 부상 위험을 줄이기 위해, 필요한 모든 물건을 꺼내되 올라가는 높이의 총합이 최소가 되도록 해야 한다. 총 높이는 모든 오르기의 높이를 더한 값이다.

보관대와 그 위에 놓인 물건들의 위치가 주어질 때, 필요한 모든 물건을 꺼내기 위한 최소 총 오르기 높이를 구하는 프로그램을 작성하시오.

첫째 줄에 두 정수 $C$와 $R$가 공백으로 구분되어 주어진다. ($1 \le C \le 100$, $1 \le R \le 100$) 각각 열의 개수와 행의 개수를 나타낸다.

둘째 줄에 꺼내야 하는 물건의 개수 $N$이 주어진다. ($1 \le N \le 100$)

다음 $N$개의 줄에는 각각 두 정수 $A$와 $B$가 공백으로 구분되어 주어진다. ($1 \le A \le C$, $1 \le B \le R$) 이는 꺼내야 하는 물건이 $A$번 열의 $B$번 행에 있음을 의미한다.

필요한 모든 물건을 꺼내기 위한 최소 총 오르기 높이를 첫째 줄에 출력한다.