Steve được tặng một chiếc bánh ga tô sinh nhật hình chữ nhật kích thước ~ m×n ~. Steve rất thích hình vuông và dự định cắt nó ra thành các miếng hình vuông. Để làm được việc đó Steve tưởng tượng chiếc bánh như một hình chữ nhật có tọa độ góc dưới trái là ~ (0, 0) ~ và tọa độ góc trên phải là ~ (m,n) ~.

Đang mãi suy nghĩ nên Steve không nhận thấy em mình đã nhanh tay cắt thực hiện ~ k ~ lần cắt, mỗi lát cắt song song với cạnh của chiếc bánh và đi suốt toàn bộ bánh. Điều này làm Steve hết sức buồn rầu chán nản và quyết định chỉ cắt một miếng hình vuông lớn nhất đặt lên bàn.

Yêu cầu: Cho ~ n, m, k ~ và các lát cắt ~ t_i, v_i ~, trong đó ~ t_i = 0 ~ xác định lát cắt ~ x=v_i ~ ~ (0 ≤ x ≤ n) ~, ~ t_i = 1 ~ xác định lát cắt ~ y = v_i ~ ~ (0 ≤ y ≤ m) ~. Hãy xác định độ dài ~ d ~ cạnh hình vuông lớn nhất có thể cắt.

Dữ liệu vào

• Dòng đầu tiên chứa 3 số nguyên ~ n,m,k ~ ~ (1≤ n, m ≤ 10^9, 0 ≤ k ≤ 10^5) ~
• Dòng thứ ~ i ~ trong ~ k ~ dòng sau chứa 2 số nguyên ~ t_i, v_i ~.

Kết quả

• Ghi ra số nguyên ~ d ~.

Ví dụ:

Input 1

10 10 2
1 5
0 3 

Output 1

5