{"raw_statement":[{"iden":"statement","content":"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.\n\nNow, 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!\n\nThe 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 <= n <= 10^9$, $1 <= x, y <= n$, and $1 <= k <= n^2$)\n\nNote, $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).\n\nOutput a single number, representing the minimum number of seconds until at least $k$ squares in the grid are covered in slime.\n\nIn the first example, the slime starts off in one grid square at time $0$ (namely position $(3, 2)$) which is $>= 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.\n\n"},{"iden":"input","content":"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 <= n <= 10^9$, $1 <= x, y <= n$, and $1 <= k <= 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)."},{"iden":"output","content":"Output a single number, representing the minimum number of seconds until at least $k$ squares in the grid are covered in slime."},{"iden":"examples","content":"Input4 3 2 1\nOutput0\nInput10 7 3 7\nOutput2\n"},{"iden":"note","content":"In the first example, the slime starts off in one grid square at time $0$ (namely position $(3, 2)$) which is $>= 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."}],"translated_statement":null,"sample_group":[],"show_order":[],"formal_statement":"**Definitions**  \nLet $ n \\in \\mathbb{Z}^+ $ be the side length of the grid.  \nLet $ (x, y) \\in \\{1, \\dots, n\\}^2 $ be the initial position of the slime.  \nLet $ k \\in \\mathbb{Z}^+ $ be the minimum number of squares to be covered.  \n\n**Constraints**  \n1. $ 1 \\leq n \\leq 10^9 $  \n2. $ 1 \\leq x, y \\leq n $  \n3. $ 1 \\leq k \\leq n^2 $  \n\n**Objective**  \nFind the minimum non-negative integer $ t $ such that the number of grid squares reachable from $ (x, y) $ in at most $ t $ steps (Manhattan distance $ \\leq t $) and within the bounds $ [1, n] \\times [1, n] $ is at least $ k $.  \n\nThat is, compute:  \n$$\n\\min \\left\\{ t \\in \\mathbb{Z}_{\\geq 0} \\,\\middle|\\, \\left| \\left\\{ (i, j) \\in [1, n]^2 \\,\\middle|\\, |i - x| + |j - y| \\leq t \\right\\} \\right| \\geq k \\right\\}\n$$","simple_statement":"A slime starts at position (x, y) on an n×n grid. Each second, it spreads to all 4 adjacent squares (up, down, left, right). Find the minimum seconds needed for at least k squares to be covered.","has_page_source":false}