(maxpiece.*)

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 \times 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 toạ độ góc trái dưới là \((0,0)\) và toạ độ gó 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 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 bánh 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 \leq x \leq n)\), \(t_{i} = 1\) xác định lát cắt \(y = v_{i}\) \((0 \leq y \leq 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 \leq n,m \leq 10^{9};0 \leq k \leq 10^{5})\)

+ Dòng thứ \(i\) trong \(k\) dòng tiếp theo mỗi dòng chứa 2 số nguyên \(t_{I},\ v_{i}\)

Kết quả:

+ Ghi ra số nguyên \(d\)

Ví dụ: