Shelves

Time limit1sMemory limit128 MB

Summary

Given required shelf positions in a grid, choose one ladder placement height per column to minimize the total summed climbing height covering each object from its column or adjacent columns.

Level: Medium6 of 10
Topics: Dynamic programming, Greedy, Array
Solved: No attempts yet

Problem

A storage rack in a police station is made up of shelves arranged in $C$ columns and $R$ rows.

To take an object off a shelf you must use a ladder. A ladder can be leaned against a single column of shelves only. If you lean the ladder against a column and climb it to a certain height (row), you can take any object located at or below that height, both from that column and from the columns immediately to its left and right.

In other words, leaning the ladder against column $c$ and climbing to height $h$ lets you take every object placed in rows $1$ through $h$ of columns $c-1$ , $c$ , and $c+1$ . (There is no column to the left of the leftmost column or to the right of the rightmost one.)

The officers need to take certain objects off the rack. To reduce the risk of injury, they want to take all of the required objects while keeping the total climbing height as small as possible. The total height is the sum of the heights of all climbs.

Given the rack and the positions of the objects placed on it, write a program that finds the minimum possible total climbing height needed to collect every required object.

Input

The first line contains two integers $C$ and $R$ separated by a space ( $1 \le C \le 100$ , $1 \le R \le 100$ ), the number of columns and the number of rows.

The second line contains an integer $N$ ( $1 \le N \le 100$ ), the number of objects that must be reached.

Each of the next $N$ lines contains two integers $A$ and $B$ separated by a space ( $1 \le A \le C$ , $1 \le B \le R$ ), meaning that an object to be reached is located in column $A$ , row $B$ .

Output

Print, on a single line, the minimum possible total climbing height needed to reach all of the given objects.

Examples5

Example 1
Input
```
5 5
3
2 3
3 4
4 4
```
Expected output
```
4
```
Example 2
Input
```
6 20
4
5 6
1 1
6 1
3 7
```
Expected output
```
9
```
Example 3
Input
```
10 10
5
9 1
7 6
5 8
4 1
3 2
```
Expected output
```
11
```
Example 4
Input
```
1 1
1
1 1
```
Expected output
```
1
```
Example 5
Input
```
2 10
2
1 5
2 8
```
Expected output
```
8
```