Боб и Кэрол провели целый день вместе с Алисой, но пришла пора идти домой. Алиса, Боб и Кэрол живут на бесконечной двумерной плоскости в клетках \(A\), \(B\) и \(C\) соответственно. Сейчас все трое находятся в клетке \(A\).
Если Боб (или Кэрол) находится в некоторой клетке, то он (она) может переместиться в одну из ее соседних клеток. Две клетки называются соседними, если они имеют общую сторону. Например, у клетки \((3, 5)\) есть четыре соседние клетки: \((2, 5)\), \((4, 5)\), \((3, 6)\) и \((3, 4)\).
Боб хочет вернуться в клетку \(B\), Кэрол — в клетку \(C\). Каждый из них хочет вернуться домой по кратчайшему пути, т. е. по пути, который состоит из наименьшего возможного количества клеток. Но также они хотели бы идти вместе.
Какое наибольшее возможное количество клеток Боб и Кэрол смогут пройти вместе, если каждых из них идет домой по одному из кратчайших путей?
Выходные данные
Для каждого набора входных данных, выведите одно целое число — максимально возможное количество клеток, которые Боб и Кэрол могут пройти вместе, если каждый из них идет домой по одному из кратчайших путей.
Примечание
Во всех картинках, красным обозначены клетки, лежащие только на пути Боба; светло-синим — клетки на пути только Кэрол, а темно-синим — общие для Боба и Кэрол клетки.
Один из оптимальных ответов для первого набора входных данных изображен ниже:
Путь Боба состоит из
\(5\) клеток, путь Кэрол — из
\(7\) клеток, и они пройдут
\(3\) клетки вместе.
Оптимальный ответ для второго набора изоборажен ниже:
Путь Боба состоит из
\(4\) клеток, путь Кэрол — из
\(3\) клеток, и они пройдут вместе только
\(1\) клетку.
Один из оптимальных ответов для третьего набора изображен ниже:
Путь Боба состоит из
\(6\) клеток, путь Кэрол — из
\(9\) клеток, и они пройдут
\(6\) клеток вместе.
Примеры
| № | Входные данные | Выходные данные |
|
1
|
3
3 1
1 3
6 4
5 2
2 2
7 2
1 1
4 3
5 5
|
3
1
6
|