Welcome to the Adelaide University Cosmology & Propulsion Laboratory (AUCPL).

In just a few moments, you and your team will be launching toward TRAPPIST-1, a distant solar system home to eight Earth-like planets. Your mission: establish first contact with intelligent life, and finally prove that humanity is not alone in the universe.

But first, you need to escape Earth's atmosphere.

We'll model the planet's surface as an ~n \times m~ grid. Your rocket begins at ground level, in the bottom-left corner at row ~n-1~ and column ~0~, or ~(n-1, 0)~. Your goal is to reach any square on the top row ~(0, ?)~, that is, to break through the atmosphere and head for the stars.

Unfortunately, you didn't pick the best day to launch. Clouds are drifting across the grid and wreaking havoc on your fuel efficiency. You'll want to avoid them as much as possible if you hope to reach orbit. Each minute, two things occur:

• You must move your rocket one square in any of the four cardinal directions (up, down, left, or right), staying within the bounds of the grid.
• Then, all clouds shift one square to the left. If a cloud moves past the left edge of the grid, it wraps around to the right side (toroidal movement).

What is the minimum number of clouds you need to hit, while successfully escaping Earth's atmosphere?

Input

The first line consists of two integers ~n~ ~(2 \leq n \leq 1000)~ and ~m~ ~(2 \leq m \leq 20)~, the size of the Earth's atmosphere.

The next line consists of a single integer ~k~ ~(1 \leq k \leq n \times m)~, the number of clouds in the atmosphere.

The next ~k~ lines contain ~r~ and ~c~ ~(0 \leq r \leq n-1, 0 \leq c \leq m-1)~, indicating that there is a cloud starting at ~(r, c)~ on the grid.

Output

Output the minimum number of clouds you are required to hit reach any cell ~(0, ?)~ after starting from cell ~(n-1, 0)~.

Clarifications

• Your rocket will never start on a cloud.
• Your rocket moves first, then the clouds.
• You can run into a cloud twice in the same minute: first when you move, then when the clouds move.
• If a cloud collides with you after you reach ~(0, ?)~, the collision is still counted.
• Although the clouds can move off the left edge of the grid and wrap around to the right, your rocket cannot.

Example

Input 1

4 4
5
3 1
2 0
1 1
1 2
0 3

Output 1

1

In this case, you can't avoid running into at least ~1~ cloud.

Input 2

4 4
8
0 0
0 1
0 2
0 3
2 0
2 1
2 2
2 3

Output 2

4

In this case, you can't avoid running into at least ~4~ clouds. You will run into one moving up at any point, then the clouds will move left, making you run into another one.

Input 3

2 2
1
0 0

Output 3

1

Input 4

2 2
1
0 1

Output 4

1