선반

시간 제한1초메모리 제한128 MB

요약

각 열마다 사다리를 놓고 올라갈 높이를 정해, 인접한 세 열 범위 안의 모든 목표 물건을 커버하면서 높이의 총합을 최소화하는 문제입니다.

난이도: 보통10점 중 6점
유형: 동적 계획법, 그리디, 배열
정답자: 아직 제출이 없습니다

문제

경찰서의 물품 보관대는 $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$ 번 행에 있음을 의미한다.

출력

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

예제5

예제 1
입력
```
5 5
3
2 3
3 4
4 4
```
예상 출력
```
4
```
예제 2
입력
```
6 20
4
5 6
1 1
6 1
3 7
```
예상 출력
```
9
```
예제 3
입력
```
10 10
5
9 1
7 6
5 8
4 1
3 2
```
예상 출력
```
11
```
예제 4
입력
```
1 1
1
1 1
```
예상 출력
```
1
```
예제 5
입력
```
2 10
2
1 5
2 8
```
예상 출력
```
8
```