Mr. Bender has a digital table of size n × n, each cell can be switched on or off. He wants the field to have at least c switched on squares. When this condition is fulfilled, Mr Bender will be happy.

We'll consider the table rows numbered from top to bottom from 1 to n, and the columns — numbered from left to right from 1 to n. Initially there is exactly one switched on cell with coordinates (x, y) (x is the row number, y is the column number), and all other cells are switched off. Then each second we switch on the cells that are off but have the side-adjacent cells that are on.

For a cell with coordinates (x, y) the side-adjacent cells are cells with coordinates (x - 1, y), (x + 1, y), (x, y - 1), (x, y + 1).

In how many seconds will Mr. Bender get happy?

Input

The first line contains four space-separated integers n, x, y, c (1 ≤ n, c ≤ 109; 1 ≤ x, y ≤ n; c ≤ n2).

Output

In a single line print a single integer — the answer to the problem.

Examples

Input

6 4 3 1


Output

0


Input

9 3 8 10


Output

2

Note

Initially the first test has one painted cell, so the answer is 0. In the second test all events will go as is shown on the figure. <image>.
import sys

def out1( k , n ) :
    if k >= n :
        return 0
    n -= k
    return n * n

def out2( x , y , n ) :
    n -= x + y + 1
    if n <= 0 :
        return 0
    return n * ( n + 1 ) / 2

def ins( n ) :
    return ( n + 1 ) * ( n + 1 ) + n * n 

def turned( n, x, y, k ) :
    res =  ins( k )
    res -= out1( x , k ) + out1( y, k ) + out1( n - 1 - x , k ) + out1( n - 1 - y , k )
    res += out2( x , y , k ) + out2( n - 1 - x , y , k ) + out2( x , n - 1 - y , k ) + out2( n - 1 - x , n - 1 - y , k )
    return res

def main() :
    n, x, y, c = [ int( x ) for x in sys.stdin.readline().strip().split() ]
    x, y = x-1 , y-1
    low = -1
    high = 1000000
    while high > low + 1 :
        mid = ( high + low ) / 2
        c0 = turned( n, x, y, mid )
        if c0 < c :
            low = mid
        else :
            high = mid
    print high
    
    
        

if __name__ == "__main__" :
    main()
