407401: GYM102784 H Slime-inator

Dr. Heinz Doofenshmirtz has been waiting to get his revenge on the Tri-state Area and his 'perfect' brother, Mayor Roger Doofenshmirtz. Mayor Doofenshmirtz and the prodigal twins, Phineas and Ferb, have organized a city-wide trick-or-treat scavenger hunt for the city's children. Dr. Doofenshirmtz figures that this is his chance to sabotage his brother's popularity and creates the 'Slime-inator', a device that fills the streets with a gooey slime that makes it impossible to walk or drive around, never mind trick-or-treat. Major Monogram, as always, has got wind of Doofenshmirtz's evil plan and calls for his trusty agent, Perry the Platypus, to save the kids trick-or-treat experience.

Now, the city of Danville was meticulously planned when it was built so it can be broken down into an $$$n \times n$$$ square grid with each of the squares having equal size. Dr. Doofenshmirtz releases his slime from Doofenshmirtz Tower at position $$$(x,y)$$$ in the grid at time $$$t=0$$$ seconds. Each second, the slime moves into each of the four adjacent squares of anywhere it is at currently (so if it is currently at $$$(x,y)$$$ it will go to $$$(x-1,y)$$$, $$$(x+1,y)$$$, $$$(x,y-1)$$$, and $$$(x,y+1)$$$ in the next second - provided all those locations are in the range of the city, Doofenshmirtz is environmentally conscious so he has engineered the slime to not cross the borders of the city grid). The trick-or-treat event will be completely ruined and unsalvageable if at least $$$k$$$ of the city's grid squares are covered by slime. Help Perry determine the number of seconds it will take for at least $$$k$$$ of the squares in the grid of the city to be covered in slime so that he can get to Doofenshmirtz in time and save the trick-or-treat event!

The first line of input will contain four space-separated integers, $$$n$$$, $$$x$$$, $$$y$$$, and $$$k$$$ representing the side length of the city grid, the row in the grid Doofenshmirtz tower is at, the column in the grid Doofenshmirtz tower is at, and the number of grid squares that must be covered before the event is unsalvageable, respectively. ($$$1 \leq n \leq 10^{9}$$$, $$$1 \leq x,y \leq n$$$, and $$$1 \leq k \leq n^{2}$$$)

Note, $$$k$$$ can be up to $$$10^{18}$$$ (if $$$n = 10^{9}$$$) so use your language's appropriate data type for these values and corresponding computations (long in Java and long long in C++ for example).

Output a single number, representing the minimum number of seconds until at least $$$k$$$ squares in the grid are covered in slime.

4 3 2 1

0

10 7 3 7

2

In the first example, the slime starts off in one grid square at time $$$0$$$ (namely position $$$(3,2)$$$) which is $$$\geq k$$$ meaning that Perry was too late and the event is already unsalvageable. In the second case, after $$$1$$$ second, the slime will cover $$$5$$$ grid squares and then after $$$2$$$ seconds, it will cover $$$13$$$ squares which is more than $$$k$$$ so Perry must stop Doofenshmirtz before $$$2$$$ seconds passes.