A hard problem to be solved in python

Time limit: 5 seconds!

Memory limit: 256 Mb!

You have your favourite field where you like to walk and relax.

Field is a rectangle N M meters. You usually start your walk in the North-West (left top) point of the field with coordinates (0, 0), and finish it in the South-East (right bottom) point with coordinates (N-1, M-1). As you don't want to make extra movements, you usually make steps only to the East or to the South (right or down).

Recently you have found out that this field will be turned into the park soon. On the field K trees will be planted. Filed will be divided into cells 1 1 meter, and each tree will take one whole cell, so, if two trees are planted in neighbour cells, you can't go between them. You love parks, but you are worried if your walks will still be possible.

You have found a plan with information on where the trees will be planted and the order in which they will be planted. You want to know, when your usual walks will become impossible.

Input format

First line of input file contains three integer numbers N, M, K: 2 N, M 300; 1 K < N M.

Each of next K lines contains two integer numbers: (i_k, j_k) coordinates of k-th tree (i number of row, j number of column): 0 i_k < N; 0 j_k < M. Trees are given in order in which they will be planted, and enumerated from 0. It is guaranteed that no trees will be planted in (0, 0).

Output format

Print single integer number minimum index of tree (trees are enumerated from 0) after which your usual walks will become impossible, or -1 if that will not happen.

Sample 1

Input	Output
3 4 5 0 2 0 3 2 0 1 1 2 2	3

Sample 2

Input	Output
3 4 5 0 2 0 3 2 0 1 3 2 1	-1

Sample 3

Input	Output
3 3 2 0 1 1 0	1