Problem: Bob is playing a popular game called "Dungeon". The game is played on a rectangular board consisting of W × H squares. Each square is identified with its column and row number, thus the square located in the x-th column and the y-th row is represented as (x, y). The left-most square in the top row is (0, 0) and the right-most square in the bottom row is (W-1, H-1).

Bob moves a character "BomBom" to clear the game. BomBom is initially located at (0, 0). The game is won if Bob successfully destroys all the enemy characters on the board by manipulating BomBom cleverly. The enemy characters are fixed on specific squares, and Bob can manipulate BomBom using the following two operations any number of times.

* One-square movement in the up, down, left, or right direction within the board
* Using a bomb, eliminate all the enemy characters that are located in the same column and row as that of BomBom



BomBom consumes a Cost when it moves from one square to another. BomBom can use a bomb any number of times without consuming a Cost. Use of a bomb has no effect on BomBom’s behavior and it can move even to a square where an enemy character is located.

Given the board size and enemy information, make a program to evaluate the minimum Cost BomBom consumes before it destroys all enemy characters.



Input

The input is given in the following format.


W H N
x_1 y_1
x_2 y_2
:
x_N y_N


The first line provides the number of squares in the horizontal direction W (1 ≤ W ≤ 105), in the vertical direction H (1 ≤ H ≤ 105), and the number of enemy characters N (1 ≤ N ≤ 105). Each of the subsequent N lines provides location information of the i-th enemy, column x_i (0 ≤ x_i ≤ W-1) and row y_i (0 ≤ y_i ≤ H-1). The number of enemy characters in a specific square can be either one or zero.

Output

Output the minimum Cost in a line.

Examples

Input

5 4 4
0 3
1 1
2 2
2 3


Output

2


Input

6 6 5
2 1
5 2
3 3
1 4
1 5


Output

4


Input

8 8 4
6 0
7 0
0 6
0 7


Output

0

Solution (in CPP):

Solution:
#include "bits/stdc++.h"
using namespace std;
typedef long long ll;
#define _overload4(_1,_2,_3,_4,name,...) name
#define _overload3(_1,_2,_3,name,...) name
#define _overload2(_1,_2,name,...) name
#define _re(n) _rep(i,n)
#define _rep(i,n) _repi(i,0,n)
#define _repi(i,a,b) for(ll i=a;i<b;++i)
#define _repc(i,a,b,c) for(ll i=a;i<b;i+=c)
#define rep(...) _overload4(__VA_ARGS__,_repc,_repi,_rep,_re)(__VA_ARGS__)
#define _rre(n) _rrep(i,n)
#define _rrep(i,n) _rrepi(i,0,n)
#define _rrepi(i,a,b) for(ll i=b-1;i>=a;i--)
#define _rrepc(i,a,b,c) for(ll i=a+(b-a-1)/c*c;i>=a;i-=c)
#define rrep(...) _overload4(__VA_ARGS__,_rrepc,_rrepi,_rrep,_rre)(__VA_ARGS__)
#define sum(...) accumulate(range(__VA_ARGS__),0)
#define _range(i) (i).begin(),(i).end()
#define _rangek(i,k) (i).begin(),(i).begin()+k
#define range(...) _overload2(__VA_ARGS__,_rangek,_range)(__VA_ARGS__)
#define LINF (ll)1000000000000000000
#define MOD (ll)1000000007
#define INF (int)1000000007
#define Yes(i) out(i?"Yes":"No")
#define YES(i) out(i?"YES":"NO")
#define INT(...) int __VA_ARGS__;in(__VA_ARGS__)
#define LL(...) ll __VA_ARGS__;in(__VA_ARGS__)
#define STR(...) string __VA_ARGS__;in(__VA_ARGS__)
#define CHR(...) char __VA_ARGS__;in(__VA_ARGS__)
#define DBL(...) double __VA_ARGS__;in(__VA_ARGS__)
#define vec(type,name,size) vector<type> name(size);
#define VEC(type,name,size) vector<type> name(size);in(name)
struct aaa{aaa(){cin.tie(0); cout.tie(0); ios::sync_with_stdio(0); cout<<fixed<<setprecision(15);};}aaaaaaa;
inline void in() {}
template<typename T>
istream& operator >> (istream& is, vector<T>& vec);
template<typename T,typename L>
istream& operator >> (istream& is, pair<T,L>& p);
template<typename T>
ostream& operator << (ostream& os, vector<T>& vec);
template<typename T,typename L>
ostream& operator << (ostream& os, pair<T,L>& p);
template<typename T>
istream& operator >> (istream& is, vector<T>& vec){for(T& x: vec) is >> x;return is;}
template<typename T,typename L>
istream& operator >> (istream& is, pair<T,L>& p){is >> p.first;is >> p.second;return is;}
template<typename T>
ostream& operator << (ostream& os, vector<T>& vec){os << vec[0];rep(i,1,vec.size()){os << ' ' << vec[i];}return os;}
template<typename T,typename L>
ostream& operator << (ostream& os, pair<T,L>& p){os << p.first << " " << p.second;return os;}
template <class Head, class... Tail>
inline void in(Head&& head,Tail&&... tail){cin>>head;in(move(tail)...);}
template <class T>
inline void out(T t){cout<<t<<'\n';}
inline void out(){cout<<'\n';}
template <class Head, class... Tail>
inline void out(Head head,Tail... tail){cout<<head<<' ';out(move(tail)...);}


int main(){
    INT(w,h,n);
    vec(int,a,w);
    rep(i,0,n){
        INT(x,y);
        if(a[x]<y)a[x]=y;
    }
    rrep(i,0,w-1){
        if(a[i]<a[i+1])a[i]=a[i+1];
    }
    rep(i,0,w-1)a[i]=i+a[i+1];
    a[w-1]=w-1;
    out(*min_element(range(a)));
}