Нью-Йорк представляет собой прямоугольную сетку, состоящую из N вертикальных авеню, пронумерованных от 1 до N, и M горизонтальных улиц, пронумерованных от 1 до M. C друзей остановились в C отелях, расположенных на пересечениях некоторых улиц с некоторыми авеню. Они собираются отметить день рождения одного из них в одном из H ресторанов, также расположенных в пересечениях некоторых авеню и улиц. При этом они хотят, чтобы максимальное среди расстояний, которые требуется проехать друзьям, чтобы добраться до ресторана, было как можно меньше. Помогите друзьям выбрать ресторан для вечеринки.
Считайте, что расстояние между соседними перекрёстками по вертикали и по горизонтали одинаковое и составляет один километр.
Выходные данные
В первой строке выходных данных выведите одно число — искомое оптимальное расстояние. В следующей строке выведите номер любого из ресторанов, гарантирующих данное расстояние. Если вариантов ответа несколько, выведите любой.
Примеры
| № | Входные данные | Выходные данные |
|
1
|
10 10
2
1 1
3 3
2
1 10
4 4
|
6
2
|