D. Остап и квадрат
ограничение по времени на тест
2 секунды
ограничение по памяти на тест
256 мегабайт
ввод
stdin
вывод
stdout

У Остапа есть электронная таблица размера n × n, каждая клетка которой может быть выключена или включена. Он хочет чтобы на поле были включены не менее чем c клеток, когда это условие будет выполнено — Остап станет счастливым.

Будем считать, что строки таблицы пронумерованы сверху вниз от 1 до n, а столбцы — слева направо от 1 до n. Изначально включена ровно одна клетка с координатами (x, y) (x — номер строки, y — номер столбца), а все остальные клетки находятся в выключенном состоянии. Далее каждую секунду происходит включение выключенных клеток, у которых есть включенные соседние по стороне клетки.

Для клетки с координатами (x, y) соседними по стороне являются клетки с координатами (x - 1, y), (x + 1, y), (x, y - 1), (x, y + 1).

Через сколько секунд Остап станет счастливым?

Входные данные

В первой строке содержится четыре целых числа, разделенных пробелами, n, x, y, c (1 ≤ n, c ≤ 109; 1 ≤ x, y ≤ nc ≤ n2).

Выходные данные

В единственную строку выведите целое число — ответ на задачу.

Примеры
Входные данные
6 4 3 1
Выходные данные
0
Входные данные
9 3 8 10
Выходные данные
2
Примечание

В первом тесте изначально закрашена одна клетка, по этому ответ 0. Во втором тесте все события будут происходить как показано на картинке. .