Задача D. Максимальный квадрат

Автор:Сборы   Ограничение времени:3 сек
Входной файл:square.in   Ограничение памяти:200 Мб
Выходной файл:square.out  

Условие

На плоскости задан прямоугольник размером W × H, и N отмеченных точек внутри него. Требуется найти квадрат максимального размера:

Формат входного файла

Первая строка входного файла содержит числа N — количество отмеченных точек, W — ширину прямоугольника и H — высоту прямоугольника. Следующие N строк содержат координаты отмеченных точек Xi, Yi (целые числа, 0 ≤ Xi ≤ W, 0 ≤ Yi ≤ H). Система координат введена так, что вершины прямоугольника имеют координаты (0, 0), (W, 0), (0, H), (W, H).

Формат выходного файла

Выведите в выходной файл одно число — длину стороны максимального искомого квадрата.

Ограничения

1 ≤ N ≤ 30000

0 ≤ W, H ≤ 1000000.

Примеры тестов

Входной файл (square.in) Выходной файл (square.out)
1
7 10 7
3 2
4 2
7 0
7 3
4 5
2 4
1 7
4
2
1 10 10
5 5
5

0.038s 0.008s 15